\documentclass[a4paper]{article}

\def\npart {IA}
\def\nterm {Michaelmas}
\def\nyear {2014}
\def\nlecturer {J.\ Goedecke}
\def\ncourse {Groups}

\input{header}

\begin{document}
\maketitle
{\small
  \noindent\textbf{Examples of groups}\\
  Axioms for groups. Examples from geometry: symmetry groups of regular polygons, cube, tetrahedron. Permutations on a set; the symmetric group. Subgroups and homomorphisms. Symmetry groups as subgroups of general permutation groups. The M\"obius group; cross-ratios, preservation of circles, the point at infinity. Conjugation. Fixed points of M\"obius maps and iteration.\hspace*{\fill} [4]

  \vspace{10pt}
  \noindent\textbf{Lagrange's theorem}\\
  Cosets. Lagrange's theorem. Groups of small order (up to order 8). Quaternions. Fermat-Euler theorem from the group-theoretic point of view.\hspace*{\fill} [5]

  \vspace{10pt}
  \noindent\textbf{Group actions}\\
  Group actions; orbits and stabilizers. Orbit-stabilizer theorem. Cayley's theorem (every group is isomorphic to a subgroup of a permutation group). Conjugacy classes. Cauchy's theorem.\hspace*{\fill} [4]

  \vspace{10pt}
  \noindent\textbf{Quotient groups}\\
  Normal subgroups, quotient groups and the isomorphism theorem.\hspace*{\fill} [4]

  \vspace{10pt}
  \noindent
  \textbf{Matrix groups}\\
  The general and special linear groups; relation with the M\"obius group. The orthogonal and special orthogonal groups. Proof (in $\R^3$) that every element of the orthogonal group is the product of reflections and every rotation in $\R^3$ has an axis. Basis change as an example of conjugation.\hspace*{\fill} [3]

  \vspace{10pt}
  \noindent\textbf{Permutations}\\
  Permutations, cycles and transpositions. The sign of a permutation. Conjugacy in $S_n$ and in $A_n$. Simple groups; simplicity of $A_5$.\hspace*{\fill} [4]}
\tableofcontents

\setcounter{section}{-1}
\section{Introduction}
Group theory is an example of \emph{algebra}. In pure mathematics, algebra (usually) does not refer to the boring mindless manipulation of symbols. Instead, in algebra, we have some set of objects with some operations on them. For example, we can take the integers with addition as the operation. However, in algebra, we allow \emph{any} set and \emph{any} operations, not just numbers.

Of course, such a definition is too broad to be helpful. We categorize algebraic structures into different types. In this course, we will study a particular kind of structures, \emph{groups}. In the IB Groups, Rings and Modules course, we will study rings and modules as well.

These different kinds of structures are defined by certain \emph{axioms}. The \emph{group axioms} will say that the operation must follow certain rules, and any set and operation that satisfies these rules will be considered to form a group. We will then have a different set of axioms for rings, modules etc.

As mentioned above, the most familiar kinds of algebraic structures are number systems such as integers and rational numbers. The focus of group theory, however, is not on things that resemble ``numbers''. Instead, it is the study of \emph{symmetries}.

First of all, what is a symmetry? We are all familiar with, say, the symmetries of an (equilateral) triangle (we will always assume the triangle is equilateral). We rotate a triangle by $120^\circ$, and we get the original triangle. We say that rotating by $120^\circ$ is a symmetry of a triangle. In general, a symmetry is something we do to an object that leaves the object intact.

Of course, we don't require that the symmetry leaves \emph{everything} intact. Otherwise, we would only be allowed to do nothing. Instead, we require certain important things to be intact. For example, when considering the symmetries of a triangle, we only care about how the resultant object looks, but don't care about where the individual vertices went.

In the case of the triangle, we have six symmetries: three rotations (rotation by $0^\circ, 120^\circ$ and $240^\circ$), and three reflections along the axes below:
\begin{center}
  \begin{tikzpicture}
    \foreach \x in {0,120,240} {
      \begin{scope}[rotate=\x]
        \draw (-1, -0.577) -- (1, -0.577);
        \draw [mred, dashed] (0, -1.2) -- (0, 1.778);
      \end{scope}
    }
  \end{tikzpicture}
\end{center}
These six together form the underlying set of the \emph{group of symmetries}. A more sophisticated example is the symmetries of $\R^3$. We define these as operations on $\R^3$ that leave distances between points unchanged. These include translations, rotations, reflections, and combinations of these.

So what is the operation? This operation combines two symmetries to give a new symmetry. The natural thing to do is to do the symmetry one after another. For example, if we combine the two $120^\circ$ rotations, we get a $240^\circ$ rotation.

Now we are studying algebra, not geometry. So to define the group, we \emph{abstract away} the triangle. Instead, we define the group to be six objects, say $\{e, r, r^2, s, rs, r^2s\}$, with rules defining how we combine two elements to get a third. Officially, we do not mention the triangle at all when defining the group.

We can now come up with the group axioms. What rules should the set of symmetries obey? First of all, we must have a ``do nothing'' symmetry. We call this the \emph{identity} element. When we compose the identity with another symmetry, the other symmetry is unchanged.

Secondly, given a symmetry, we can do the reverse symmetry. So for any element, there is an inverse element that, when combined with the original, gives the identity.

Finally, given three symmetries, we can combine them, one after another. If we denote the operation of the group as $*$, then if we have three symmetries, $x, y, z$, we should be able to form $x*y*z$. If we want to define it in terms of the binary operation $*$, we can define it as $(x*y)*z$, where we first combine the first two symmetries, then combine the result with the third. Alternatively, we can also define it as $x*(y*z)$. Intuitively, these two should give the same result, since both are applying $x$ after $y$ after $z$. Hence we have the third rule $x*(y*z) = (x*y)*z$.

Now a group is any set with an operation that satisfies the three rules above. In group theory, the objective is to study the properties of groups just assuming these three axioms. It turns out that there is a \emph{lot} we can talk about.

\section{Groups and homomorphisms}
\subsection{Groups}
\begin{defi}[Binary operation]
  A \emph{(binary) operation} is a way of combining two elements to get a new element. Formally, it is a map $*: A \times A \rightarrow A$.
\end{defi}
\begin{defi}[Group]
  A \emph{group} is a set $G$ with a binary operation $*$ satisfying the following axioms:
  \begin{enumerate}[label=\arabic{*}.]
    \item There is some $e \in G$ such that for all $a$, we have
      \[
        a*e = e*a = a.\tag{identity}
      \]
    \item For all $a \in G$, there is some $a^{-1} \in G$ such that
      \[
        a*a^{-1} = a^{-1}*a = e.\tag{inverse}
      \]
    \item For all $a, b, c\in G$, we have
      \[
        (a*b)*c = a*(b*c).\tag{associativity}
      \]
  \end{enumerate}
\end{defi}

\begin{defi}[Order of group]
  The \emph{order} of the group, denoted by $|G|$, is the number of elements in $G$. A group is a finite group if the order is finite.
\end{defi}

Note that \emph{technically}, the inverse axiom makes no sense, since we have not specified what $e$ is. Even if we take it to be the $e$ given by the identity axiom, the identity axiom only states there is \emph{some} $e$ that satisfies that property, but there could be many! We don't know which one $a * a^{-1}$ is supposed to be equal to! So we should technically take that to mean there is some $a^{-1}$ such that $a*a^{-1}$ and $a^{-1} * a$ satisfy the identity axiom. Of course, we will soon show that identities are indeed unique, and we will happily talk about ``the'' identity.

Some people put a zeroth axiom called ``closure'':
\begin{enumerate}[label=\arabic{*}.]
    \setcounter{enumi}{-1}
  \item For all $a, b \in G$, we have $a * b \in G$.\hfill (closure)
\end{enumerate}
Technically speaking, this axiom also makes no sense --- when we say $*$ is a binary operation, by definition, $a * b$ \emph{must} be a member of $G$. However, in practice, we often have to check that this axiom actually holds. For example, if we let $G$ be the set of all matrices of the form
\[
  \begin{pmatrix}
    1 & x & y\\
    0 & 1 & z\\
    0 & 0 & 1
  \end{pmatrix}
\]
under matrix multiplication, we will have to check that the product of two such matrices is indeed a matrix of this form. Officially, we are checking that the binary operation is a well-defined operation on $G$.

It is important to know that it is generally \emph{not} true that $a*b = b*a$. There is no \emph{a priori} reason why this should be true. For example, if we are considering the symmetries of a triangle, rotating and then reflecting is different from reflecting and then rotating.

However, for some groups, this happens to be true. We call such groups \emph{abelian groups}.
\begin{defi}[Abelian group]
  A group is \emph{abelian} if it satisfies
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{3}
    \item $(\forall a, b \in G)\, a*b = b*a$. \hfill (commutativity)
  \end{enumerate}
\end{defi}
If it is clear from context, we are lazy and leave out the operation $*$, and write $a*b$ as $ab$. We also write $a^2 = aa$, $a^n = \underbrace{aaa\cdots a}_{n \text{ copies}}$, $a^0 = e$, $a^{-n} = (a^{-1})^n$ etc.
\begin{eg}
  The following are abelian groups:
  \begin{enumerate}
    \item $\Z$ with $+$
    \item $\Q$ with $+$
    \item $\Z_n$ (integers mod $n$) with $+_n$
    \item $\Q^*$ with $\times$
    \item $\{-1, 1\}$ with $\times$
  \end{enumerate}
  The following are non-abelian groups:
  \begin{enumerate}[resume]
    \item Symmetries of an equilateral triangle (or any $n$-gon) with composition. ($D_{2n}$)
    \item $2\times 2$ invertible matrices with matrix multiplication ($\GL_2(\R)$)
    \item Symmetry groups of 3D objects
  \end{enumerate}
\end{eg}

Recall that the first group axiom requires that there exists \emph{an} identity element, which we shall call $e$. Then the second requires that for each $a$, there is an inverse $a^{-1}$ such that $a^{-1}a = e$. This only makes sense if there is only one identity $e$, or else which identity should $a^{-1}a$ be equal to?

We shall now show that there can only be one identity. It turns out that the inverses are also unique. So we will talk about \emph{the} identity and \emph{the} inverse.
\begin{prop}
  Let $(G, *)$ be a group. Then
  \begin{enumerate}
    \item The identity is unique.
    \item Inverses are unique.
  \end{enumerate}
\end{prop}
\begin{proof}\leavevmode
  \begin{enumerate}[label=(\roman{*})]
    \item Suppose $e$ and $e'$ are identities. Then we have $ee' = e'$, treating $e$ as an inverse, and $ee' = e$, treating $e'$ as an inverse. Thus $e = e'$.
    \item Suppose $a^{-1}$ and $b$ both satisfy the inverse axiom for some $a\in G$. Then $b = be = b(aa^{-1}) = (ba)a^{-1} = ea^{-1} = a^{-1}$. Thus $b = a^{-1}$.\qedhere
  \end{enumerate}
\end{proof}
\begin{prop}
  Let $(G, *)$ be a group and $a, b\in G$. Then
  \begin{enumerate}
    \item $(a^{-1})^{-1} = a$
    \item $(ab)^{-1} = b^{-1}a^{-1}$
  \end{enumerate}
\end{prop}
\begin{proof}\leavevmode
  \begin{enumerate}
    \item Given $a^{-1}$, both $a$ and $(a^{-1})^{-1}$ satisfy
      \[
        xa^{-1} = a^{-1}x = e.
      \]
      By uniqueness of inverses, $(a^{-1})^{-1} = a$.
    \item We have
      \begin{align*}
        (ab)(b^{-1}a^{-1}) &= a(bb^{-1})a^{-1} \\
        &= aea^{-1}\\
        &= aa^{-1}\\
        &= e
      \end{align*}
      Similarly, $(b^{-1}a^{-1})ab = e$. So $b^{-1}a^{-1}$ is an inverse of $ab$. By the uniqueness of inverses, $(ab)^{-1} = b^{-1}a^{-1}$.\qedhere
  \end{enumerate}
\end{proof}

Sometimes if we have a group $G$, we might want to discard some of the elements. For example if $G$ is the group of all symmetries of a triangle, we might one day decide that we hate reflections because they reverse orientation. So we only pick the rotations in $G$ and form a new, smaller group. We call this a \emph{subgroup} of $G$.

\begin{defi}[Subgroup]
  A $H$ is a \emph{subgroup} of $G$, written $H\leq G$, if $H\subseteq G$ and $H$ with the restricted operation $*$ from $G$ is also a group.
\end{defi}
\begin{eg}\leavevmode
  \begin{itemize}
    \item $(\Z, +)\leq (\Q, +) \leq (\R, +)\leq (\C, +)$
    \item $({e}, *) \leq (G, *)$ (trivial subgroup)
    \item $G \leq G$
    \item $(\{\pm 1\}, \times) \leq (\Q^*, \times)$
  \end{itemize}
\end{eg}

According to the definition, to prove that $H$ is a subgroup of $G$, we need to make sure $H$ satisfies all group axioms. However, this is often tedious. Instead, there are some simplified criteria to decide whether $H$ is a subgroup.
\begin{lemma}[Subgroup criteria I]
  Let $(G, *)$ be a group and $H\subseteq G$. $H \leq G$ iff
  \begin{enumerate}
    \item $e \in H$
    \item $(\forall a, b\in H)\,ab \in H$
    \item $(\forall a \in H)\,a^{-1} \in H$
  \end{enumerate}
\end{lemma}
\begin{proof}
  The group axioms are satisfied as follows:
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item Closure: (ii)
    \item Identity: (i). Note that $H$ and $G$ must have the same identity. Suppose that $e_H$ and $e_G$ are the identities of $H$ and $G$ respectively. Then $e_He_H = e_H$. Now $e_H$ has an inverse in $G$. Thus we have $e_He_He_H^{-1} = e_He_H^{-1}$. So $e_He_G = e_G$. Thus $e_H = e_G$.
    \item Inverse: (iii)
    \item Associativity: inherited from $G$.\qedhere
  \end{enumerate}
\end{proof}
Humans are lazy, and the test above is still too complicated. We thus come up with an even simpler test:

\begin{lemma}[Subgroup criteria II]
  A subset $H\subseteq G$ is a subgroup of $G$ iff:
  \begin{enumerate}[label=(\Roman{*})]
    \item $H$ is non-empty
    \item $(\forall a, b\in H)\,ab^{-1}\in H$
  \end{enumerate}
\end{lemma}
\begin{proof}
  (I) and (II) follow trivially from (i), (ii) and (iii).

  To prove that (I) and (II) imply (i), (ii) and (iii), we have
  \begin{enumerate}
    \item $H$ must contain at least one element $a$. Then $aa^{-1} = e \in H$.
      \setcounter{enumi}{2}
    \item $ea^{-1} = a^{-1} \in H$.
      \setcounter{enumi}{1}
    \item $a(b^{-1})^{-1} = ab\in H$.
  \end{enumerate}
\end{proof}
\begin{prop}
  The subgroups of $(\Z, +)$ are exactly $n\Z$, for $n\in \N$ ($n\Z$ is the integer multiples of $n$).
\end{prop}
\begin{proof}
  Firstly, it is trivial to show that for any $n \in \N$, $n\Z$ is a subgroup. Now show that any subgroup must be in the form $n\Z$.

  Let $H\leq \Z$. We know $0\in H$. If there are no other elements in $H$, then $H = 0\Z$. Otherwise, pick the smallest positive integer $n$ in $H$. Then $H=n\Z$.

  Otherwise, suppose $(\exists a\in H)\,n \nmid a$. Let $a = pn + q$, where $0 < q < n$. Since $a - pn\in H$, $q\in H$. Yet $q < n$ but $n$ is the smallest member of $H$. Contradiction. So every $a\in H$ is divisible by $n$. Also, by closure, all multiples of $n$ must be in $H$. So $H = n\Z$.
\end{proof}
\subsection{Homomorphisms}
It is often helpful to study functions between different groups. First, we need to define what a function is. These definitions should be familiar from IA Numbers and Sets.

\begin{defi}[Function]
  Given two sets $X$, $Y$, a \emph{function} $f: X \rightarrow Y$ sends each $x\in X$ to a particular $f(x)\in Y$. $X$ is called the domain and $Y$ is the co-domain.
\end{defi}
\begin{eg}\leavevmode
  \begin{itemize}
    \item Identity function: for any set $X$, $1_X: X \rightarrow X$ with $1_X(x) = x$ is a function. This is also written as $\mathrm{id}_X$.
    \item Inclusion map: $\iota: \Z \rightarrow \Q$: $\iota(n) = n$. Note that this differs from the identity function as the domain and codomain are different in the inclusion map.
    \item $f_1: \Z \rightarrow \Z$: $f_1(x) = x + 1$.
    \item $f_2: \Z \rightarrow \Z$: $f_2(x) = 2x$.
    \item $f_3: \Z \rightarrow \Z$: $f_3(x) = x^2$.
    \item For $g: \{0, 1, 2, 3, 4\} \rightarrow \{0, 1, 2, 3, 4\}$, we have:
      \begin{itemize}
        \item $g_1(x) = x + 1$ if $x < 4$; $g_1(4) = 4$.
        \item $g_2(x) = x + 1$ if $x < 4$; $g_1(4) = 0$.
      \end{itemize}
  \end{itemize}
\end{eg}
\begin{defi}[Composition of functions]
  The \emph{composition} of two functions is a function you get by applying one after another. In particular, if $f: X \rightarrow Y$ and $G: Y\rightarrow Z$, then $g\circ f: X \rightarrow Z$ with $g\circ f(x) = g(f(x))$.
\end{defi}
\begin{eg}
  $f_2\circ f_1(x) = 2x + 2$. $f_1\circ f_2 (x) = 2x + 1$. Note that function composition is not commutative.
\end{eg}
\begin{defi}[Injective functions]
  A function $f$ is \emph{injective} if it hits everything at most once, i.e.
  \[
    (\forall x, y\in X)\,f(x) = f(y)\Rightarrow x = y.
  \]
\end{defi}

\begin{defi}[Surjective functions]
  A function is \emph{surjective} if it hits everything at least once, i.e.
  \[
    (\forall y\in Y)(\exists x\in X)\,f(x) = y.
  \]
\end{defi}

\begin{defi}[Bijective functions]
  A function is \emph{bijective} if it is both injective and surjective. i.e.\ it hits everything exactly once. Note that a function has an inverse iff it is bijective.
\end{defi}

\begin{eg}
  $\iota$ and $f_2$ are injective but not subjective. $f_3$ and $g_1$ are neither. $1_X$, $f_1$ and $g_2$ are bijective.
\end{eg}

\begin{lemma}
  The composition of two bijective functions is bijective
\end{lemma}

When considering sets, functions are allowed to do all sorts of crazy things, and can send any element to any element without any restrictions. However, we are currently studying groups, and groups have additional structure on top of the set of elements. Hence we are not interested in arbitrary functions. Instead, we are interested in functions that ``respect'' the group structure. We call these \emph{homomorphisms}.
\begin{defi}[Group homomorphism]
  Let $(G, *)$ and $(H, \times)$ be groups. A function $f:G\rightarrow H$ is a \emph{group homomorphism} iff
  \[
   ( \forall g_1, g_2 \in G)\, f(g_1)\times f(g_2) = f(g_1 * g_2),
  \]
\end{defi}

\begin{defi}[Group isomorphism]
  \emph{Isomorphisms} are bijective homomorphisms. Two groups are \emph{isomorphic} if there exists an isomorphism between them. We write $G\cong H$.
\end{defi}
We will consider two isomorphic groups to be ``the same''. For example, when we say that there is only one group of order $2$, it means that any two groups of order $2$ must be isomorphic.

\begin{eg}\leavevmode
  \begin{itemize}
    \item $f: G \to H$ defined by $f(g) = e$, where $e$ is the identity of $H$, is a homomorphism.
    \item $1_G: G \rightarrow G$ and $f_2: \Z \rightarrow 2\Z$ are isomorphisms. $\iota: \Z\rightarrow\Q$ and $f_2:\Z\rightarrow\Z$ are homomorphisms.
    \item $\mathrm{exp}: (\R, +) \rightarrow (\R^+, \times)$ with $\mathrm{exp}(x) = e^x$ is an isomorphism.
    \item Take $(\Z_4, +)$ and $H: (\{e^{ik\pi/2}:k=0, 1 ,2, 3\}, \times)$. Then $f: \Z_4 \rightarrow H$ by $f(a) = e^{i\pi a/2}$ is an isomorphism.
    \item $f: \GL_2(\R) \rightarrow \R^*$ with $f(A) = \det(A)$ is a homomorphism, where $\GL_2(\R)$ is the set of $2\times 2$ invertible matrices.
  \end{itemize}
\end{eg}

\begin{prop}
  Suppose that $f: G\rightarrow H$ is a homomorphism. Then
  \begin{enumerate}
    \item Homomorphisms send the identity to the identity, i.e.
      \[
        f(e_G) = e_H
      \]
    \item Homomorphisms send inverses to inverses, i.e.
      \[
        f(a^{-1}) = f(a)^{-1}
      \]
    \item The composite of 2 group homomorphisms is a group homomorphism.
    \item The inverse of an isomorphism is an isomorphism.
  \end{enumerate}
\end{prop}
\begin{proof}\leavevmode
  \begin{enumerate}
    \item \begin{align*}
        f(e_G) &= f(e_G^2) = f(e_G)^2\\
        f(e_G)^{-1}f(e_G) &= f(e_G)^{-1}f(e_G)^2\\
        f(e_G) &= e_H
      \end{align*}
    \item \begin{align*}
        e_H &= f(e_G)\\
        &= f(aa^{-1})\\
        &= f(a)f(a^{-1})
      \end{align*}
      Since inverses are unique, $f(a^{-1}) = f(a)^{-1}$.
    \item Let $f:G_1 \rightarrow G_2$ and $g:G_2 \rightarrow G_3$. Then $g(f(ab)) = g(f(a)f(b)) = g(f(a))g(f(b))$.
    \item Let $f:G \rightarrow H$ be an isomorphism. Then
      \begin{align*}
        f^{-1}(ab) &= f^{-1}\Big\{f\big[f^{-1}(a)\big]f\big[f^{-1}(b)\big]\Big\}\\
        &= f^{-1}\Big\{f\big[f^{-1}(a)f^{-1}(b)\big]\Big\}\\
        &= f^{-1}(a)f^{-1}(b)
      \end{align*}
      So $f^{-1}$ is a homomorphism. Since it is bijective, $f^{-1}$ is an isomorphism.\qedhere
  \end{enumerate}
\end{proof}

\begin{defi}[Image of homomorphism]
  If $f:G\rightarrow H$ is a homomorphism, then the \emph{image} of $f$ is
  \[
    \im f = f(G) = \{f(g):g\in G\}.
  \]
\end{defi}

\begin{defi}[Kernel of homomorphism]
  The \emph{kernel} of $f$, written as
  \[
    \ker f = f^{-1}(\{e_H\}) = \{g\in G:f(g)=e_H\}.
  \]
\end{defi}

\begin{prop}
  Both the image and the kernel are subgroups of the respective groups, i.e.\ $\im f\leq H$ and $\ker f \leq G$.
\end{prop}

\begin{proof}
  Since $e_H\in \im f$ and $e_G\in \ker f$, $\im f$ and $\ker f$ are non-empty. Moreover, suppose $b_1, b_2\in \im f$. Now $\exists a_1, a_2 \in G$ such that $f(a_i) = b_i$. Then $b_1b_2^{-1} = f(a_1)f(a_2^{-1}) = f(a_1a_2^{-1})\in \im f$.

  Then consider $b_1,b_2\in \ker f$. We have $f(b_1b_2^{-1}) = f(b_1)f(b_2)^{-1} = e^2 = e$. So $b_1b_2^{-1}\in \ker f$.
\end{proof}

\begin{prop}
  Given any homomorphism $f:G\rightarrow H$ and any $a\in G$, for all $k\in \ker f$, $aka^{-1}\in\ker f$.
\end{prop}
This proposition seems rather pointless. However, it is not. All subgroups that satisfy this property are known as \emph{normal subgroups}, and normal subgroups have very important properties. We will postpone the discussion of normal subgroups to later lectures.

\begin{proof}
  $f(aka^{-1}) = f(a)f(k)f(a)^{-1} = f(a)ef(a)^{-1} = e$. So $aka^{-1}\in \ker f$.
\end{proof}

\begin{eg}
  Images and kernels for previously defined functions:
  \begin{enumerate}
    \item For the function that sends everything to $e$, $\im f = \{e\}$ and $\ker f = G$.
    \item For the identity function, $\im 1_G = G$ and $\ker 1_G = \{e\}$.
    \item For the inclusion map $\iota: \Z\rightarrow\Q$, we have $\im \iota = \Z$ and $\ker \iota = \{0\}$
    \item For $f_2:\Z\rightarrow\Z$ and $f_2(x) = 2x$, we have $\im f_2 = 2\Z$ and $\ker f_2 = \{0\}$.
    \item For $\det: \GL_2(\R) \rightarrow \R^*$, we have $\im \det = \R^*$ and $\ker \det = \{A:\det A = 1\} = \mathrm{SL}_2(\R)$
  \end{enumerate}
\end{eg}
\begin{prop}
  For all homomorphisms $f:G\rightarrow H$, $f$ is
  \begin{enumerate}
    \item surjective iff $\im f = H$
    \item injective iff $\ker f = \{e\}$
  \end{enumerate}
\end{prop}

\begin{proof}\leavevmode
  \begin{enumerate}
    \item By definition.
    \item We know that $f(e) = e$. So if $f$ is injective, then by definition $\ker f = \{e\}$. If $\ker f = \{e\}$, then given $a, b$ such that $f(a) = f(b)$, $f(ab^{-1}) = f(a)f(b)^{-1} = e$. Thus $ab^{-1}\in \ker f = \{e\}$. Then $ab^{-1} = e$ and $a = b$.\qedhere
  \end{enumerate}
\end{proof}

So far, the definitions of images and kernels seem to be just convenient terminology to refer to things. However, we will later prove an important theorem, the \emph{first isomorphism theorem}, that relates these two objects and provides deep insights (hopefully).

Before we get to that, we will first study some interesting classes of groups and develop some necessary theory.

\subsection{Cyclic groups}
The simplest class of groups is \emph{cyclic groups}. A cyclic group is a group of the form $\{e, a, a^2, a^2, \cdots, a^{n - 1}\}$, where $a^n = e$. For example, if we consider the group of all rotations of a triangle, and write $r = $ rotation by $120^\circ$, the elements will be $\{e, r, r^2\}$ with $r^3 = e$.

Officially, we define a cyclic group as follows:
\begin{defi}[Cyclic group $C_n$]
  A group $G$ is \emph{cyclic} if
  \[
    (\exists a)(\forall b)(\exists n\in\Z)\, b = a^n,
  \]
  i.e.\ every element is some power of $a$. Such an $a$ is called a generator of $G$.

  We write $C_n$ for the cyclic group of order $n$.
\end{defi}

\begin{eg}\leavevmode
  \begin{enumerate}
    \item $\Z$ is cyclic with generator $1$ or $-1$. It is \emph{the} infinite cyclic group.
    \item $(\{+1, -1\}, \times)$ is cyclic with generator $-1$.
    \item $(\Z_n, +)$ is cyclic with all numbers coprime with $n$ as generators.
  \end{enumerate}
\end{eg}

\begin{notation}
  Given a group $G$ and $a\in G$, we write $\bra a\ket$ for the cyclic group generated by $a$, i.e.\ the subgroup of all powers of $a$. It is the smallest subgroup containing $a$.
\end{notation}

\begin{defi}[Order of element]
  The \emph{order} of an element $a$ is the smallest integer $n$ such that $a^n = e$. If $n$ doesn't exist, $a$ has infinite order. Write $\ord(a)$ for the order of $a$.
\end{defi}
We have given two different meanings to the word ``order''. One is the order of a group and the other is the order of an element. Since mathematicians are usually (but not always) sensible, the name wouldn't be used twice if they weren't related. In fact, we have

\begin{lemma}
  For $a$ in $g$, $\ord (a) = |\bra a\ket|$.
\end{lemma}
\begin{proof}
  If $\ord (a) = \infty$, $a^n \not= a^m$ for all $n\not= m$. Otherwise $a^{m-n} = e$. Thus $|\bra a\ket| = \infty = \ord (a)$.

  Otherwise, suppose $\ord (a) = k$. Thus $a^k = e$. We now claim that $\bra a\ket = \{e, a^1, a^2, \cdots a^{k-1}\}$. Note that $\bra a\ket$ does not contain higher powers of $a$ as $a^k = e$ and higher powers will loop back to existing elements. There are also no repeating elements in the list provided since $a^m = a^n \Rightarrow a^{m-n} = e$. So done.
\end{proof}

It is trivial to show that
\begin{prop}
  Cyclic groups are abelian.
\end{prop}

\begin{defi}[Exponent of group]
  The \emph{exponent} of a group $G$ is the smallest integer $n$ such that $a^n = e$ for all $a \in G$.
\end{defi}

\subsection{Dihedral groups}
\begin{defi}[Dihedral groups $D_{2n}$]
  Dihedral groups are the symmetries of a regular $n$-gon. It contains $n$ rotations (including the identity symmetry, i.e.\ rotation by $0^\circ$) and $n$ reflections.

  We write the group as $D_{2n}$. Note that the subscript refers to the order of the group, not the number of sides of the polygon.
\end{defi}

The dihedral group is not hard to define. However, we need to come up with a presentation of $D_{2n}$ that is easy to work with.

We first look at the rotations. The set of all rotations is generated by $r = \frac{360^\circ}{n}$. This $r$ has order $n$.

How about the reflections? We know that each reflection has order $2$. Let $s$ be our favorite reflection. Then using some geometric arguments, we can show that any reflection can be written as a product of $r^m$ and $s$ for some $m$. We also have $srs = r^{-1}$.

Hence we can define $D_{2n}$ as follows: $D_{2n}$ is a group generated by $r$ and $s$, and every element can be written as a product of $r$'s and $s$'s. Whenever we see $r^n$ and $s^2$, we replace it by $e$. When we see $srs$, we replace it by $r^{-1}$.

It then follows that every element can be written in the form $r^m s$.

Formally, we can write $D_{2n}$ as follows:
\begin{align*}
  D_{2n} &= \bra r, s\mid r^n=s^2=e, srs^{-1} = r^{-1}\ket\\
  &= \{e, r, r^2, \cdots r^{n-1}, s, rs, r^2s, \cdots r^{n-1}s\}
\end{align*}
This is a notation we will commonly use to represent groups. For example, a cyclic group of order $n$ can be written as
\[
  C_n = \bra a\mid a^n =e \ket.
\]

\subsection{Direct products of groups}
Recall that if we have to sets $X, Y$, then we can obtain the product $X\times Y = \{(x, y): x\in X, y\in Y\}$. We can do the same if $X$ and $Y$ are groups.

\begin{defi}[Direct product of groups]
  Given two groups $(G, \circ)$ and $(H, \bullet)$, we can define a set $G\times H = \{(g, h): g\in G, h\in H\}$ and an operation $(a_1, a_2)*(b_1, b_2) = (a_1\circ b_1, a_2\bullet b_2)$. This forms a group.
\end{defi}

Why would we want to take the product of two groups? Suppose we have two independent triangles. Then the symmetries of this system include, say rotating the first triangle, rotating the second, or rotating both. The symmetry group of this combined system would then be $D_6 \times D_6$.

\begin{eg}
  \begin{align*}
    C_2\times C_2 &= \{(0, 0), (0, 1), (1, 0), (1, 1)\}\\
    &= \{e, x, y, xy\} \text{ with everything order 2}\\
    &= \bra x, y\mid x^2=y^2=e, xy = yx\ket
  \end{align*}
\end{eg}

\begin{prop}
  $C_n\times C_m\cong C_{nm}$ iff $\hcf(m, n) = 1$.
\end{prop}

\begin{proof}
  Suppose that $\hcf(m, n) = 1$. Let $C_n = \bra a\ket$ and $C_m = \bra b \ket$. Let $k$ be the order of $(a, b)$. Then $(a, b)^k = (a^k, b^k) = e$. This is possible only if $n \mid k$ and $m \mid k$, i.e.\ $k$ is a common multiple $n$ and $m$. Since the order is the minimum value of $k$ that satisfies the above equation, $k = \lcm(n, m) = \frac{nm}{\hcf(n, m)} = nm$.

  Now consider $\bra (a, b)\ket \leq C_n\times C_m$. Since $(a, b)$ has order $nm$, $\bra (a, b)\ket$ has $nm$ elements. Since $C_n\times C_m$ also has $nm$ elements, $\bra (a, b)\ket$ must be the whole of $C_n\times C_m$. And we know that $\bra (a, b)\ket\cong C_{nm}$. So $C_n\times C_m \cong C_{nm}$.

  On the other hand, suppose $\hcf(m, n) \not= 1$. Then $k = \lcm(m, n) \not= mn$. Then for any $(a, b)\in C_n \times C_m$,we have $(a, b)^k = (a^k, b^k) = e$. So the order of any $(a, b)$ is at most $k < mn$. So there is no element of order $mn$. So $C_n\times C_m$ is not a cyclic group of order $nm$.
\end{proof}

Given a complicated group $G$, it is sometimes helpful to write it as a product $H\times K$, which could make things a bit simpler. We can do so by the following theorem:
\begin{prop}[Direct product theorem]
  Let $H_1, H_2\leq G$. Suppose the following are true:
  \begin{enumerate}
    \item $H_1\cap H_2 = \{e\}$.
    \item $(\forall a_i\in H_i)\, a_1a_2=a_2a_1$.
    \item $(\forall a\in G)(\exists a_i\in H_i)\,a = a_1a_2$. We also write this as $G=H_1H_2$.
  \end{enumerate}
  Then $G\cong H_1\times H_2$.
\end{prop}

\begin{proof}
  Define $f:H_1\times H_2\rightarrow G$ by $f(a_1, a_2) = a_1a_2$. Then it is a homomorphism since
  \begin{align*}
    f((a_1, a_2)*(b_1,b_2)) &= f(a_1b_1, a_2b_2)\\
    &= a_1b_1a_2b_2\\
    &= a_1a_2b_1b_2\\
    &= f(a_1, a_2)f(b_1,b_2).
  \end{align*}
  Surjectivity follows from (iii). We'll show injectivity by showing that the kernel is $\{e\}$. If $f(a_1, a_2)=e$, then we know that $a_1a_2 = e$. Then $a_1=a_2^{-1}$. Since $a_1 \in H_1$ and $a_2^{-1} \in H_2$, we have $a_1 = a_2^{-1} \in H_1\cap H_2 = \{e\}$. Thus $a_1 = a_2 = e$ and $\ker f = \{e\}$.
\end{proof}

\section{Symmetric group I}
We will devote two full chapters to the study of symmetric groups, because it is really important. Recall that we defined a symmetry to be an operation that leaves some important property of the object intact. We can treat each such operation as a bijection. For example, a symmetry of $\R^2$ is a bijection $f: \R^2 \to \R^2$ that preserves distances. Note that we must require it to be a bijection, instead of a mere function, since we require each symmetry to be an inverse.

We can consider the case where we don't care about anything at all. So a ``symmetry'' would be any arbitrary bijection $X \to X$, and the set of all bijections will form a group, known as the \emph{symmetric group}. Of course, we will no longer think of these as ``symmetries'' anymore, but just bijections.

In some sense, the symmetric group is the most general case of a symmetry group. In fact, we will later (in Chapter~\ref{sec:action}) show that every group can be written as a subgroup of some symmetric group.
\subsection{Symmetric groups}
\begin{defi}[Permutation]
  A \emph{permutation} of $X$ is a bijection from a set $X$ to $X$ itself. The set of all permutations on $X$ is $\Sym X$.
\end{defi}
When composing permutations, we treat them as functions. So if $\sigma$ and $\rho$ are permutations, $\sigma\circ \rho$ is given by first applying $\rho$, then applying $\sigma$.

\begin{thm}
  $\Sym X$ with composition forms a group.
\end{thm}

\begin{proof}
  The groups axioms are satisfied as follows:
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item If $\sigma: X\to X$ and $\tau: X\to X$, then $\sigma\circ\tau:X\to X$. If they are both bijections, then the composite is also bijective. So if $\sigma, \tau\in \Sym X$, then $\sigma\circ\tau\in\Sym X$.
    \item The identity $1_X:X\to X$ is clearly a permutation, and gives the identity of the group.
    \item Every bijective function has a bijective inverse. So if $\sigma\in \Sym X$, then $\sigma^{-1} \in \Sym X$.
    \item Composition of functions is associative.\qedhere
  \end{enumerate}
\end{proof}

\begin{defi}[Symmetric group $S_n$]
  If $X$ is finite, say $|X| = n$ (usually use $X = \{1, 2, \cdots, n\}$), we write $\Sym X = S_n$. The is the \emph{symmetric group} of degree $n$.
\end{defi}
It is important to note that the \emph{degree} of the symmetric group is different from the \emph{order} of the symmetric group. For example, $S_3$ has degree 3 but order 6. In general, the order of $S_n$ is $n!$.

There are two ways to write out an element of the symmetric group. The first is the \emph{two row notation}.
\begin{notation}
  (Two row notation) We write $1, 2, 3, \cdots n$ on the top line and their images below, e.g.
  \[
    \begin{pmatrix}
      1 & 2 & 3\\
      2 & 3 & 1
    \end{pmatrix}\in S_3 \text{ and }
    \begin{pmatrix}
      1 & 2 & 3 & 4 & 5\\
      2 & 1 & 3 & 4 & 5
    \end{pmatrix}\in S_5
  \]
  In general, if $\sigma: X\to X$, we write
  \[
    \begin{pmatrix}
      1 & 2 & 3 &\cdots& n\\
      \sigma(1) & \sigma(2)&\sigma(3) &\cdots& \sigma{(n)}
    \end{pmatrix}
  \]
\end{notation}

\begin{eg}
  For small $n$, we have
  \begin{enumerate}
    \item When $n = 1$, $S_n = \left\{\begin{pmatrix}1\\1\end{pmatrix}\right\} = \{e\}\cong C_1$.
    \item When $n = 2$, $S_n = \left\{\begin{pmatrix}1 & 2\\ 1 & 2\end{pmatrix}, \begin{pmatrix}1 & 2\\2 & 1\end{pmatrix}\right\}\cong C_2$
    \item When $n = 3$,
      \[
        S_n = \left\{\begin{matrix}\begin{pmatrix}1 & 2 & 3\\1 & 2 & 3\end{pmatrix}, &\begin{pmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix}, &\begin{pmatrix}1 & 2 & 3\\3 & 1 & 2\end{pmatrix}\\\\\begin{pmatrix}1 & 2 & 3\\2 & 1 & 3\end{pmatrix}, &\begin{pmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}, &\begin{pmatrix}1 & 2 & 3\\1 & 3 & 2\end{pmatrix}\end{matrix}\right\}\cong D_6.
      \]
      Note that $S_3$ is not abelian. Thus $S_n$ is not abelian for $n \geq 3$ since we can always view $S_3$ as a subgroup of $S_n$ by fixing $4, 5, 6, \cdots n$.
  \end{enumerate}
\end{eg}
In general, we can view $D_{2n}$ as a subgroup of $S_n$ because each symmetry is a permutation of the corners.

While the two row notation is fully general and can represent any (finite) permutation, it is clumsy to write and wastes a lot of space. It is also very annoying to type using \LaTeX. Hence, most of the time, we actually use the cycle notation.

\begin{notation}[Cycle notation]
  If a map sends $1 \mapsto 2$, $2\mapsto 3$, $3\mapsto 1$, then we write it as a cycle $(1\;2\;3)$. Alternatively, we can write $(2\;3\;1)$ or $(3\;1\;2)$, but by convention, we usually write the smallest number first. We leave out numbers that don't move. So we write $(1\; 2)$ instead of $(1\; 2)(3)$.

  For more complicated maps, we can write them as products of cycles. For example, in $S_4$, we can have things like $(1\; 2)(3\; 4)$.
\end{notation}
The order of each cycle is the length of the cycle, and the inverse is the cycle written the other way round, e.g.\ $(1\; 2\; 3)^{-1} = (3\; 2\; 1) = (1\; 3\; 2)$.

\begin{eg}\leavevmode
  \begin{enumerate}
    \item Suppose we want to simplify $(1\; 2\; 3)(1\; 2)$. Recall that composition is from right to left. So $1$ gets mapped to $3$ ($(1\; 2)$ maps $1$ to $2$, and $(1\; 2\; 3)$ further maps it to $3$). Then $3$ gets mapped to $1$. $2$ is mapped to $2$ itself. So $(1\; 2\; 3)(1\; 2) = (1\;3)(2)$
    \item $(1\; 2\; 3\; 4)(1\; 4) = (1)(2\; 3\; 4) = (2\; 3\; 4)$.
  \end{enumerate}
\end{eg}
\begin{defi}[$k$-cycles and transpositions]
  We call $(a_1\; a_2\; a_3\cdots a_k)$ a \emph{$k$-cycle}. $2$-cycles are called \emph{transpositions}. Two cycles are \emph{disjoint} if no number appears in both cycles.
\end{defi}
\begin{eg}
  $(1\; 2)$ and $(3\; 4)$ are disjoint but $(1\; 2\; 3)$ and $(1\; 2)$ are not.
\end{eg}
\begin{lemma}
  Disjoint cycles commute.
\end{lemma}
\begin{proof}
  If $\sigma, \tau\in S_n$ are disjoint cycles. Consider any $n$. Show that: $\sigma(\tau(a)) = \tau(\sigma(a))$. If $a$ is in neither of $\sigma$ and $\tau$, then $\sigma(\tau(a)) = \tau(\sigma(a)) = a$. Otherwise, wlog assume that $a$ is in $\tau$ but not in $\sigma$. Then $\tau(a)\in \tau$ and thus $\tau(a)\not\in \sigma$. Thus $\sigma(a) = a$ and $\sigma(\tau(a)) = \tau(a)$. Therefore we have $\sigma(\tau(a)) = \tau(\sigma(a)) = \tau(a)$. Therefore $\tau$ and $\sigma$ commute.
\end{proof}
In general, non-disjoint cycles may not commute. For example, $(1\; 3)(2\; 3) = (1\; 3\; 2)$ while $(2\; 3)(1\; 3) = (1\; 2\; 3)$.

\begin{thm}
  Any permutation in $S_n$ can be written (essentially) uniquely as a product of disjoint cycles. (Essentially unique means unique up to re-ordering of cycles and rotation within cycles, e.g.\ $(1\; 2)$ and $(2\; 1)$)
\end{thm}

\begin{proof}
  Let $\sigma\in S_n$. Start with $(1\; \sigma(1)\; \sigma^2(1)\; \sigma^3(1)\;\cdots)$. As the set $\{1, 2, 3\cdots n\}$ is finite, for some $k$, we must have $\sigma^k(1)$ already in the list. If $\sigma^k(1) = \sigma^l(1)$, with $l < k$, then $\sigma^{k-l}(1) = 1$. So all $\sigma^i(1)$ are distinct until we get back to $1$. Thus we have the first cycle $(1\; \sigma(1)\; \sigma^2(1)\; \sigma^3(1)\;\cdots\;\sigma^{k-1}(1))$.

  Now choose the smallest number that is not yet in a cycle, say $j$. Repeat to obtain a cycle $(j\; \sigma(j)\; \sigma^2(j)\;\cdots\; \sigma^{l - 1}(j))$. Since $\sigma$ is a bijection, nothing in this cycle can be in previous cycles as well.

  Repeat until all $\{1, 2, 3\cdots n\}$ are exhausted. This is essentially unique because every number $j$ completely determines the whole cycle it belongs to, and whichever number we start with, we'll end up with the same cycle.
\end{proof}

\begin{defi}[Cycle type]
  Write a permutation $\sigma\in S_n$ in disjoint cycle notation. The \emph{cycle type} is the list of cycle lengths. This is unique up to re-ordering. We often (but not always) leave out singleton cycles.
\end{defi}
\begin{eg}
  $(1\; 2)$ has cycle type $2$ (transposition). $(1\; 2)(3\; 4)$ has cycle type $2, 2$ (double transposition). $(1\; 2\; 3)(4\; 5)$ has cycle type $3, 2$.
\end{eg}
\begin{lemma}
  For $\sigma\in S_n$, the order of $\sigma$ is the least common multiple of cycle lengths in the disjoint cycle notation. In particular, a $k$-cycle has order $k$.
\end{lemma}

\begin{proof}
  As disjoint cycles commute, we can group together each cycle when we take powers. i.e.\ if $\sigma = \tau_1\tau_2\cdots\tau_l$ with $\tau_i$ all disjoint cycles, then $\sigma^m = \tau_1^m\tau_2^m\cdots\tau_l^m$.

  Now if cycle $\tau_i$ has length $k_i$, then $\tau_i^{k_i} = e$, and $\tau_i^m = e$ iff $k_i \mid m$. To get an $m$ such that $\sigma^m = e$, we need all $k_i$ to divide $m$. i.e.\ $m$ is a common multiple of $k_i$. Since the order is the least possible $m$ such that $\sigma^m = e$, the order is the least common multiple of $k_i$.
\end{proof}

\begin{eg}
  Any transpositions and double transpositions have order 2.

  $(1\; 2\; 3)(4\; 5)$ has order 6.
\end{eg}

\subsection{Sign of permutations}
To classify different permutations, we can group different permutations according to their cycle type. While this is a very useful thing to do, it is a rather fine division. In this section, we will assign a ``sign'' to each permutation, and each permutation can either be odd or even. This high-level classification allows us to separate permutations into two sets, which is also a useful notion.

To define the sign, we first need to write permutations as products of transpositions.
\begin{prop}
  Every permutation is a product of transpositions.
\end{prop}
This is not a deep or mysterious fact. All it says is that you can rearrange things however you want just by swapping two objects at a time.

\begin{proof}
  As each permutation is a product of disjoint cycles, it suffices to prove that each cycle is a product of transpositions. Consider a cycle $(a_1\; a_2\; a_3\; \cdots\; a_k)$. This is in fact equal to $(a_1\; a_2)(a_2\; a_3)\cdots (a_{k-1}\; a_k)$. Thus a $k$-cycle can be written as a product of $k - 1$ transpositions.
\end{proof}

Note that the product is not unique. For example,
\[
  (1\; 2\; 3\; 4\; 5) =(1\; 2)(2\; 3)(3\; 4)(4\; 5) = (1\; 2)(2\; 3)(1\; 2)(3\; 4)(1\; 2)(4\; 5).
\]
However, the number of terms in the product, mod 2, is always the same.

\begin{thm}
  Writing $\sigma\in S_n$ as a product of transpositions in different ways, $\sigma$ is either always composed of an even number of transpositions, or always an odd number of transpositions.
\end{thm}
The proof is rather magical.

\begin{proof}
  Write $\#(\sigma)$ for the number of cycles in disjoint cycle notation, including singleton cycles. So $\#(e) = n$ and $\#((1\; 2)) = n - 1$. When we multiply $\sigma$ by a transposition $\tau = (c\; d)$ (wlog assume $c < d$),
  \begin{itemize}
    \item If $c, d$ are in the same $\sigma$-cycle, say, $(c\; a_2\; \cdots \; a_{k - 1}\; d\; a_{k + 1}\; \cdots a_{k + l})(c\; d) = (c\; a_{k+1}\; a_{k+2}\;\cdots a_{k + l})(d\; a_2\; a_3\;\cdots\; a_{k - 1})$. So $\#(\sigma\tau) = \#(\sigma) + 1$ .
    \item If $c, d$ are in different $\sigma$-cycles, say

      $(d\; a_2\; a_3\;\cdots\;a_{k - 1})(c\; a_{k + 1}\; a_{k + 2}\;\cdots\; a_{k + l})(c\; d) $

      $=(c\; a_2\; \cdots \; a_{k - 1}\; d\; a_{k + 1}\; \cdots a_{k + l})(c\; d)(c\; d)$

      $= (c\; a_2\; \cdots \; a_{k - 1}\; d\; a_{k + 1}\; \cdots a_{k + l})$ and $\#(\sigma\tau) = \#(\sigma) - 1$.

  \end{itemize}
  Therefore for any transposition $\tau$, $\#(\sigma\tau) \equiv \#(\sigma) + 1 \pmod 2$.

  Now suppose $\sigma = \tau_1\cdots\tau_l = \tau_1'\cdots\tau_{k}'$. Since disjoint cycle notation is unique, $\#(\sigma)$ is uniquely determined by $\sigma$.

  Now we can construct $\sigma$ by starting with $e$ and multiplying the transpositions one by one. Each time we add a transposition, we increase $\#(\sigma)$ by $1 \pmod 2$. So $\#(\sigma) \equiv \#(e) + l\pmod 2$. Similarly, $\#(\sigma) \equiv \#(e) + k \pmod 2$. So $l \equiv k \pmod 2$.
\end{proof}

\begin{defi}[Sign of permutation]
  Viewing $\sigma\in S_n$ as a product of transpositions, $\sigma = \tau_1\cdots \tau_l$, we call $\sgn(\sigma) = (-1)^l$. If $\sgn(\sigma) = 1$, we call $\sigma$ an even permutation. If $\sgn(\sigma) = -1$, we call $\sigma$ an odd permutation.
\end{defi}
While $l$ itself is not well-defined, it is either always odd or always even, and $(-1)^l$ is well-defined.

\begin{thm}
  For $n\geq 2$, $\sgn : S_n \rightarrow \{\pm 1\}$ is a surjective group homomorphism.
\end{thm}
\begin{proof}
  Suppose $\sigma_1 = \tau_1\cdots \tau_{l_1}$ and $\sigma_2 = \tau'_1\cdots \tau_{l_2}$. Then $\sgn(\sigma_1\sigma_2) = (-1)^{l_1 + l_2} = (-1)^{l_1}(-1)^{l_2} = \sgn(\sigma_1)\sgn(\sigma_2)$. So it is a homomorphism.

  It is surjective since $\sgn(e) = 1$ and $\sgn((1\; 2)) = -1$.
\end{proof}

It is this was rather trivial to prove. The hard bit is showing that $\sgn$ is well defined. If a question asks you to show that $\sgn$ is a well-defined group homomorphism, you \emph{have} to show that it is well-defined.

\begin{lemma}
  $\sigma$ is an even permutation iff the number of cycles of even length is even.
\end{lemma}

\begin{proof}
  A $k$-cycle can be written as $k - 1$ transpositions. Thus an even-length cycle is odd, vice versa.

  Since $\sgn$ is a group homomorphism, writing $\sigma$ in disjoint cycle notation, $\sigma = \sigma_1\sigma_2\cdots\sigma_l$, we get $\sgn(\sigma) = \sgn(\sigma_1)\cdots \sgn(\sigma_l)$. Suppose there are $m$ even-length cycles and $n$ odd-length cycles, then $\sgn(\sigma) = (-1)^m 1^n$. This is equal to $1$ iff $(-1)^m = 1$, i.e.\ $m$ is even.
\end{proof}
Rather confusingly, odd length cycles are even, and even length cycles are odd.

\begin{defi}[Alternating group $A_n$]
  The \emph{alternating group} $A_n$ is the kernel of $\sgn$, i.e.\ the even permutations.
  Since $A_n$ is a kernel of a group homomorphism, $A_n \leq S_n$.
\end{defi}
Among the many uses of the $\sgn$ homomorphism, it is used in the definition of the determinant of a matrix: if $A_{n\times n}$ is a square matrix, then
\[
  \det A = \sum_{\sigma\in S_n}\sgn(\sigma) a_{1\sigma(1)}\cdots a_{n\sigma(n)}.
\]

\begin{prop}
  Any subgroup of $S_n$ contains either no odd permutations or exactly half.
\end{prop}

\begin{proof}
  If $S_n$ has at least one odd permutation $\tau$, then there exists a bijection between the odd and even permutations by $\sigma \mapsto \sigma\tau$ (bijection since $\sigma \mapsto \sigma \tau^{-1}$ is a well-defined inverse). So there are as many odd permutations as even permutations.
\end{proof}
After we prove the isomorphism theorem later, we can provide an even shorter proof of this.

\section{Lagrange's Theorem}
One can model a Rubik's cube with a group, with each possible move corresponding to a group element. Of course, Rubik's cubes of different sizes correspond to different groups.

Suppose I have a $4\times 4\times 4$ Rubik's cube, but I want to practice solving a $2\times 2\times 2$ Rubik's cube. It is easy. I just have to make sure every time I make a move, I move two layers together. Then I can pretend I am solving a $2\times 2\times 2$ cube. This corresponds to picking a particular subgroup of the $4\times 4\times 4$ group.

Now what if I have a $3\times 3\times 3$ cube? I can still practice solving a $2\times 2\times 2$ one. This time, I just look at the corners and pretend that the edges and centers do not exist. Then I am satisfied when the corners are in the right positions, while the centers and edges can be completely scrambled. In this case, we are not taking a subgroup. Instead, we are identifying certain moves together. In particular, we are treating two moves as the same as long as their difference is confined to the centers and edges.

Let $G$ be the $3\times 3\times 3$ cube group, and $H$ be the subgroup of $G$ that only permutes the edges and centers. Then for any $a, b\in G$, we think $a$ and $b$ are ``the same'' if $a^{-1}b \in H$. Then the set of things equivalent to $a$ is $aH = \{ah: h \in H\}$. We call this a \emph{coset}, and the set of cosets form a group.

An immediate question one can ask is: why not $Ha = \{ha: h\in H\}$? In this particular case, the two happen to be the same for all possible $a$. However, for a general subgroup $H$, they need not be. We can still define the coset $aH = \{ah: h \in H\}$, but these are less interesting. For example, the set of all $\{aH\}$ will no longer form a group. We will look into these more in-depth in the next chapter. In this chapter, we will first look at results for general cosets. In particular, we will, step by step, prove the things we casually claimed above.

\begin{defi}[Cosets]
  Let $H\leq G$ and $a\in G$. Then the set $aH =\{ah : h\in H\}$ is a \emph{left coset} of $H$ and $Ha = \{ha : h\in H\}$ is a \emph{right coset} of $H$.
\end{defi}
\begin{eg}\leavevmode
  \begin{enumerate}
    \item Take $2\Z \leq Z$. Then $6 + 2\Z = \{\text{all even numbers}\} = 0 + 2\Z$. $1 + 2\Z = \{\text{all odd numbers}\} = 17 + 2\Z$.
    \item Take $G = S_3$, let $H = \bra (1\; 2)\ket = \{e, (1\; 2)\}$. The left cosets are
      \begin{align*}
        eH = (1\; 2)H &= \{e, (1\; 2)\}\\
        (1\; 3)H = (1\; 2\; 3)H &= \{(1\; 3), (1\; 2\; 3)\}\\
        (2\; 3)H = (1\; 3\; 2)H &= \{(2\; 3), (1\; 3\; 2)\}
      \end{align*}
    \item Take $G = D_6$ (which is isomorphic to $S_3$). Recall $D_6 = \bra r, s \mid r^3 e = s^2, rs = sr^{-1}\ket$.Take $H = \bra s\ket = \{e, s\}$. We have left coset $rH = \{r, rs = sr^{-1}\}$ and the right coset $Hr = \{r, sr\}$. Thus $rH \not= Hr$.
  \end{enumerate}
\end{eg}

\begin{prop}
  $aH = bH \Leftrightarrow b^{-1}a\in H$.
\end{prop}
\begin{proof}
  $(\Rightarrow)$ Since $a\in aH$, $a\in bH$. Then $a = bh$ for some $h\in H$. So $b^{-1}a = h\in H$.

  $(\Leftarrow)$. Let $b^{-1}a = h_0$. Then $a = bh_0$. Then $\forall ah\in aH$, we have $ah = b(h_0h)\in bH$. So $aH \subseteq bH$. Similarly, $bH\subseteq aH$. So $aH = bH$.
\end{proof}

\begin{defi}[Partition]
  Let $X$ be a set, and $X_1, \cdots X_n$ be subsets of $X$. The $X_i$ are called a \emph{partition} of $X$ if $\bigcup X_i = X$ and $X_i\cap X_j = \emptyset$ for $i\not= j$. i.e.\ every element is in exactly one of $X_i$.
\end{defi}

\begin{lemma}
  The left cosets of a subgroup $H\leq G$ partition $G$, and every coset has the same size.
\end{lemma}

\begin{proof}
  For each $a\in G$, $a\in aH$. Thus the union of all cosets gives all of $G$. Now we have to show that for all $a, b\in G$, the cosets $aH$ and $bH$ are either the same or disjoint.

  Suppose that $aH$ and $bH$ are not disjoint. Let $ah_1 = bh_2 \in aH \cap bH$. Then $b^{-1}a = h_2 h_1^{-1}\in H$. So $aH = bH$.

   To show that they each coset has the same size, note that $f: H \to aH$ with $f(h) = ah$ is invertible with inverse $f^{-1}(h) = a^{-1}h$. Thus there exists a bijection between them and they have the same size.
\end{proof}

\begin{defi}[Index of a subgroup]
  The \emph{index} of $H$ in $G$, written $|G:H|$, is the number of left cosets of $H$ in $G$.
\end{defi}

\begin{thm}[Lagrange's theorem]
  If $G$ is a finite group and $H$ is a subgroup of $G$, then $|H|$ divides $|G|$. In particular,
  \[
    |H||G:H| = |G|.
  \]
\end{thm}
Note that the converse is not true. If $k$ divides $|G|$, there is not necessarily a subgroup of order $k$, e.g.\ $|A_4| = 12$ but there is no subgroup of order $6$. However, we will later see that this is true if $k$ is a prime (cf.\ Cauchy's theorem).

\begin{proof}
  Suppose that there are $|G: H|$ left cosets in total. Since the left cosets partition $G$, and each coset has size $|H|$, we have
  \[
    |H||G:H| = |G|.\qedhere
  \]
\end{proof}
Again, the hard part of this proof is to prove that the left cosets partition $G$ and have the same size. If you are asked to prove Lagrange's theorem in exams, that is what you actually have to prove.

\begin{cor}
  The order of an element divides the order of the group, i.e.\ for any finite group $G$ and $a\in G$, $\ord(a)$ divides $|G|$.
\end{cor}
\begin{proof}
  Consider the subgroup generated by $a$, which has order $\ord(a)$. Then by Lagrange's theorem, $\ord(a)$ divides $|G|$.
\end{proof}

\begin{cor}
  The exponent of a group divides the order of the group, i.e.\ for any finite group $G$ and $a\in G$, $a^{|G|} = e$.
\end{cor}

\begin{proof}
  We know that $|G| = k\ord(a)$ for some $k\in \N$. Then $a^{|G|} = (a^{\ord(a)})^k = e^k = e$.
\end{proof}

\begin{cor}
  Groups of prime order are cyclic and are generated by every non-identity element.
\end{cor}

\begin{proof}
  Say $|G| = p$. If $a\in G$ is not the identity, the subgroup generated by $a$ must have order $p$ since it has to divide $p$. Thus the subgroup generated by $a$ has the same size as $G$ and they must be equal. Then $G$ must be cyclic since it is equal to the subgroup generated by $a$.
\end{proof}

A useful way to think about cosets is to view them as equivalence classes. To do so, we need to first define what an equivalence class is.
\begin{defi}[Equivalence relation]
  An \emph{equivalence relation} $\sim$ is a relation that is reflexive, symmetric and transitive. i.e.
  \begin{enumerate}
    \item $(\forall x)\,x\sim x$ \hfill (reflexivity)
    \item $(\forall x, y)\,x\sim y \Rightarrow y\sim x$ \hfill (symmetry)
    \item $(\forall x, y, z)\,[(x\sim y) \wedge (y\sim z)\Rightarrow x\sim z]$ \hfill (transitivity)
  \end{enumerate}
\end{defi}

\begin{eg}
  The following relations are equivalence relations:
  \begin{enumerate}
    \item Consider $\Z$. The relation $\equiv_n$ defined as $a\equiv_n b \Leftrightarrow n \mid (a - b)$.
    \item Consider the set (formally: class) of all finite groups. Then ``is isomorphic to'' is an equivalence relation.
  \end{enumerate}
\end{eg}

\begin{defi}[Equivalence class]
  Given an equivalence relation $\sim$ on $A$, the \emph{equivalence class} of $a$ is
  \[
    [a]_{\sim} = [a] = \{b\in A: a\sim b\}
  \]
\end{defi}

\begin{prop}
  The equivalence classes form a partition of $A$.
\end{prop}

\begin{proof}
  By reflexivity, we have $a\in [a]$. Thus the equivalence classes cover the whole set. We must now show that for all $a, b\in A$, either $[a] = [b]$ or $[a]\cap [b]=\emptyset$.

  Suppose $[a]\cap[b]\not=\emptyset$. Then $\exists c\in [a]\cap[b]$. So $a\sim c, b\sim c$. By symmetry, $c\sim b$. By transitivity, we have $a\sim b$. Now for all $b'\in [b]$, we have $b\sim b'$. Thus by transitivity, we have $a\sim b'$. Thus $[b]\subseteq[a]$. Similarly, $[a]\subseteq[b]$ and $[a] = [b]$.
\end{proof}

\begin{lemma}
  Given a group $G$ and a subgroup $H$, define the equivalence relation on $G$ with $a\sim b$ iff $b^{-1}a\in H$. The equivalence classes are the left cosets of $H$.
\end{lemma}

\begin{proof}
  First show that it is an equivalence relation.
  \begin{enumerate}
    \item Reflexivity: Since $aa^{-1} = e\in H$, $a\sim a$.
    \item Symmetry: $a\sim b\Rightarrow b^{-1}a\in H \Rightarrow (b^{-1}a)^{-1} = a^{-1}b\in H\Rightarrow b\sim a$.
    \item Transitivity: If $a\sim b$ and $b\sim c$, we have $b^{-1}a, c^{-1}b\in H$. So $c^{-1}bb^{-1}a = c^{-1}a\in H$. So $a\sim c$.
  \end{enumerate}
  To show that the equivalence classes are the cosets, we have $a\sim b\Leftrightarrow b^{-1}a\in H \Leftrightarrow aH = bH$.
\end{proof}

\begin{eg}
  Consider $(\Z, +)$, and for fixed $n$, take the subgroup $n\Z$. The cosets are $0+ H, 1 + H, \cdots (n - 1)+H$. We can write these as $[0], [1], [2] \cdots [n]$. To perform arithmetic ``mod $n$'', define $[a] + [b] = [a + b]$, and $[a][b] = [ab]$. We need to check that it is well-defined, i.e.\ it doesn't depend on the choice of the representative of $[a]$.

  If $[a_1] = [a_2]$ and $[b_1] = [b_2]$, then $a_1 = a_2 + kn$ and $b_1 = b_2 + kn$, then $a_1 + b_1 = a_2 + b_2 + n(k + l)$ and $a_1b_1 = a_2b_2 + n(kb_2 +la_2 + kln)$. So $[a_1 + b_1] = [a_2 + b_2]$ and $[a_1b_1] = [a_2b_2]$.
\end{eg}

We have seen that $(\Z_n, +_n)$ is a group. What happens with multiplication? We can only take elements which have inverses (these are called units, cf.\ IB Groups, Rings and Modules). Call the set of them $U_n = \{[a]: (a, n) = 1\}$. We'll see these are the units.
\begin{defi}[Euler totient function]
  (Euler totient function) $\phi (n) = |U_n|$.
\end{defi}

\begin{eg}
  If $p$ is a prime, $\phi(n) = p - 1$. $\phi(4) = 2$.
\end{eg}

\begin{prop}
  $U_n$ is a group under multiplication mod $n$.
\end{prop}

\begin{proof}
  The operation is well-defined as shown above. To check the axioms:
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item Closure: if $a, b$ are coprime to $n$, then $a\cdot b$ is also coprime to $n$. So $[a], [b]\in U_n \Rightarrow [a]\cdot [b] = [a\cdot b]\in U_n$
    \item Identity: $[1]$
    \item Let $[a]\in U_n$. Consider the map $U_n \to U_n$ with $[c]\mapsto [ac]$. This is injective: if $[ac_1] = [ac_2]$, then $n $ divides $a(c_1 - c_2)$. Since $a$ is coprime to $n$, $n$ divides $c_1 - c_2$, so $[c_1] = [c_2]$. Since $U_n$ is finite, any injection ($U_n \to U_n$) is also a surjection. So there exists a $c$ such that $[ac] = [a][c] = 1$. So $[c] = [a]^{-1}$.
    \item Associativity (and also commutativity): inherited from $\Z$.\qedhere
  \end{enumerate}
\end{proof}

\begin{thm}[Fermat-Euler theorem] Let $n\in N$ and $a\in \Z$ coprime to $n$. Then
  \[
    a^{\phi(n)} \equiv 1\pmod n.
  \]
  In particular, (Fermat's Little Theorem) if $n = p$ is a prime, then for any $a$ not a multiple of $p$.
  \[
    a^{p - 1}\equiv 1\pmod p.
  \]
\end{thm}

\begin{proof}
  As $a$ is coprime with $n$, $[a]\in U_n$. Then $[a]^{|U_n|} = [1]$, i.e.\ $a^{\phi(n)} \equiv 1\pmod n$.
\end{proof}

\subsection{Small groups}
We will study the structures of certain small groups.
\begin{eg}[Using Lagrange theorem to find subgroups]
  To find subgroups of $D_{10}$, we know that the subgroups must have size 1, 2, 5 or 10:
  \begin{enumerate}[label=\arabic{*}:]
    \item $\{e\}$
    \item The groups generated by the 5 reflections of order 2
      \setcounter{enumi}{4}
    \item The group must be cyclic since it has prime order 5. It is then generated by an element of order 5, i.e.\ $r, r^2, r^3$ and $r^4$. They generate the same group $\bra r\ket$.
      \setcounter{enumi}{9}
    \item $D_{10}$
  \end{enumerate}

  As for $D_8$, subgroups must have order 1, 2, 4 or 8.
  \begin{enumerate}[label=\arabic{*}:]
    \item $\{e\}$
    \item 5 elements of order $2$, namely 4 reflections and $r^2$.
      \setcounter{enumi}{3}
    \item First consider the subgroup isomorphic to $C_4$, which is $\bra r\ket$. There are two other non-cyclic group.
      \setcounter{enumi}{7}
    \item $D_8$
  \end{enumerate}
\end{eg}

\begin{prop}
  Any group of order 4 is either isomorphic to $C_4$ or $C_2\times C_2$.
\end{prop}

\begin{proof}
  Let $|G| = 4$. By Lagrange theorem, possible element orders are $1$ ($e$ only), $2$ and $4$. If there is an element $a\in G$ of order $4$, then $G = \bra a\ket \cong C_4$.

  Otherwise all non-identity elements have order 2. Then $G$ must be abelian (For any $a, b$, $(ab)^2 = 1 \Rightarrow ab = (ab)^{-1} \Rightarrow ab = b^{-1}a^{-1} \Rightarrow ab = ba$).
  Pick $2$ elements of order 2, say $b, c\in G$, then $\bra b\ket=\{e, b\}$ and $\bra c\ket = \{e, c\}$. So $\bra b\ket\cap \bra c\ket = \{e\}$. As $G$ is abelian, $\bra b\ket$ and $\bra c\ket$ commute. We know that $bc = cb$ has order 2 as well, and is the only element of $G$ left. So $G \cong \bra b\ket\times \bra c\ket \cong C_2\times C_2$ by the direct product theorem.
\end{proof}

\begin{prop}
  A group of order $6$ is either cyclic or dihedral (i.e.\ is isomorphic to $C_6$ or $D_6$). (See proof in next section)
\end{prop}

\subsection{Left and right cosets}
As $|aH| = |H|$ and similarly $|H| = |Ha|$, left and right cosets have the same size. Are they necessarily the same? We've previously shown that they might \emph{not} be the same. In some other cases, they are.
\begin{eg}\leavevmode
  \begin{enumerate}
    \item Take $G = (\Z, +)$ and $H = 2\Z$. We have $0 + 2\Z = 2\Z + 0 = $ even numbers and $1 + 2\Z = 2\Z + 1 = $ odd numbers. Since $G$ is abelian, $aH = Ha$ for all $a, \in G$, $H\leq G$.
    \item Let $G = D_6 = \bra r, s \mid r^3 = e = s^2, rs = sr^{-1}\ket$. Let $U = \bra r\ket$. Since the cosets partition $G$, so one must be $U$ and the other $sU = \{s, sr = r^2s, sr^2 = rs\} = Us$. So for all $a\in G, aU = Ua$.
    \item Let $G = D_6$ and take $H = \bra s\ket$ . We have $H = \{e, s\}$, $rH = \{r, rs = sr^{-1}\}$ and $r^2 H = \{r^2, r^s\}$; while $H = \{e, s\}, Hr = \{r, sr\}$ and $Hr^2=\{r^2, sr^2\}$. So the left and right subgroups do not coincide.
  \end{enumerate}
\end{eg}
This distinction will become useful in the next chapter.

\section{Quotient groups}
In the previous section, when attempting to pretend that a $3\times 3\times 3$ Rubik's cube is a $2\times 2\times 2$ one, we came up with the cosets $aH$, and claimed that these form a group. We also said that this is not the case for arbitrary subgroup $H$, but only for subgroups that satisfy $aH = Ha$. Before we prove these, we first study these subgroups a bit.

\subsection{Normal subgroups}
\begin{defi}[Normal subgroup]
  A subgroup $K$ of $G$ is a \emph{normal subgroup} if
  \[
    (\forall a\in G)(\forall k\in K)\,aka^{-1}\in K.
  \]
  We write $K\lhd G$. This is equivalent to:
  \begin{enumerate}
    \item $(\forall a\in G)\,aK = Ka$, i.e.\ left coset $=$ right coset
    \item $(\forall a\in G)\,aKa^{-1} = K$ (cf.\ conjugacy classes)
  \end{enumerate}
\end{defi}

From the example last time, $H=\bra s\ket\leq D_6$ is not a normal subgroup, but $K=\bra r\ket \lhd D_6$. We know that every group $G$ has at least two normal subgroups $\{e\}$ and $G$.

\begin{lemma}\leavevmode
  \begin{enumerate}
    \item Every subgroup of index $2$ is normal.
    \item Any subgroup of an abelian group is normal.
  \end{enumerate}
\end{lemma}

\begin{proof}\leavevmode
  \begin{enumerate}
    \item If $K\leq G$ has index $2$, then there are only two possible cosets $K$ and $G\setminus K$. As $eK = Ke$ and cosets partition $G$, the other left coset and right coset must be $G\setminus K$. So all left cosets and right cosets are the same.
    \item For all $a\in G$ and $k\in K$, we have $aka^{-1} = aa^{-1}k = k\in K$.\qedhere
  \end{enumerate}
\end{proof}
\begin{prop}
  Every kernel is a normal subgroup.
\end{prop}

\begin{proof}
  Given homomorphism $f:G\rightarrow H$ and some $a\in G$, for all $k\in \ker f$, we have $f(aka^{-1}) = f(a)f(k)f(a)^{-1} = f(a)ef(a)^{-1} = e$. Therefore $aka^{-1}\in\ker f$ by definition of the kernel.
\end{proof}

In fact, we will see in the next section that all normal subgroups are kernels of some homomorphism.

\begin{eg}
  Consider $G = D_8$. Let $K = \bra r^2\ket$ is normal. Check: Any element of $G$ is either $sr^\ell$ or $r^\ell$ for some $\ell$. Clearly $e$ satisfies $aka^{-1}\in K$. Now check $r^2$: For the case of $sr^\ell$, we have $sr^\ell r^2(sr^\ell)^{-1} = sr^\ell r^2 r^{-\ell}s^{-1} = sr^2 s = ssr^{-2} = r^2$. For the case of $r^\ell$, $r^\ell r^2r^{-\ell} = r^2$.
\end{eg}

\begin{prop}
  A group of order $6$ is either cyclic or dihedral (i.e.\ $\cong C_6$ or $D_6$).
\end{prop}

\begin{proof}
  Let $|G| = 6$. By Lagrange theorem, possible element orders are $1, 2, 3$ and $6$. If there is an $a\in G$ of order $6$, then $G = \bra a\ket \cong C_6$. Otherwise, we can only have elements of orders $2$ and $3$ other than the identity. If $G$ only has elements of order 2, the order must be a power of 2 by Sheet 1 Q. 8, which is not the case. So there must be an element $r$ of order 3. So $\bra r\ket\lhd G$ as it has index $2$. Now $G$ must also have an element $s$ of order $2$ by Sheet 1 Q. 9.

  Since $\bra r\ket$ is normal, we know that $srs^{-1}\in \bra r\ket$. If $srs^{-1} = e$, then $r = e$, which is not true. If $srs^{-1} = r$, then $sr = rs$ and $sr$ has order $6$ (lcm of the orders of $s$ and $r$), which was ruled out above. Otherwise if $srs^{-1} = r^2 = r^{-1}$, then $G$ is dihedral by definition of the dihedral group.
\end{proof}

\subsection{Quotient groups}
\begin{prop}
  Let $K\lhd G$. Then the set of (left) cosets of $K$ in $G$ is a group under the operation $aK*bK = (ab)K$.
\end{prop}

\begin{proof}
  First show that the operation is well-defined. If $aK = a'K$ and $bK = b'K$, we want to show that $aK*bK = a'K * b'K$. We know that $a' = ak_1$ and $b' = bk_2$ for some $k_1, k_2\in K$. Then $a'b' = ak_1bk_2$. We know that $b^{-1}k_1b\in K$. Let $b^{-1}k_1b = k_3$. Then $k_1 b = bk_3$. So $a'b' = abk_3k_2\in (ab)K$. So picking a different representative of the coset gives the same product.
  \begin{enumerate}[label=\arabic{*}.]
    \item Closure: If $aK, bK$ are cosets, then $(ab)K$ is also a coset
    \item Identity: The identity is $eK = K$ (clear from definition)
    \item Inverse: The inverse of $aK$ is $a^{-1}K$ (clear from definition)
    \item Associativity: Follows from the associativity of $G$.\qedhere
  \end{enumerate}
\end{proof}

\begin{defi}[Quotient group]
  Given a group $G$ and a normal subgroup $K$, the \emph{quotient group} or \emph{factor group} of $G$ by $K$, written as $G/K$, is the set of (left) cosets of $K$ in $G$ under the operation $aK*bK = (ab)K$.
\end{defi}
Note that the \emph{set} of left cosets also exists for non-normal subgroups (abnormal subgroups?), but the group operation above is not well defined.

\begin{eg}\leavevmode
  \begin{enumerate}
    \item Take $G = \Z$ and $n\Z$ (which must be normal since $G$ is abelian), the cosets are $k + n\Z$ for $0 \leq k < n$. The quotient group is $\Z_n$. So we can write $\Z/(n\Z) = \Z_n$. In fact these are the only quotient groups of $\Z$ since $n\Z$ are the only subgroups.

      Note that if $G$ is abelian, $G/K$ is also abelian.
    \item Take $K = \bra r\ket \lhd D_6$. We have two cosets $K$ and $sK$. So $D_6/K$ has order 2 and is isomorphic to $C_2$.
    \item Take $K = \bra r^2\ket \lhd D_8$. We know that $G/K$ should have $\frac{8}{2} = 4$ elements. We have $G/K = \{ K, rK = r^3 K, sK = sr^2K, srK = sr^3K\}$. We see that all elements (except $K$) has order $2$, so $G/K\cong C_2\times C_2$.
  \end{enumerate}
\end{eg}
Note that quotient groups are \emph{not} subgroups of $G$. They contain different kinds of elements. For example, $\Z/n\Z \cong C_n$ are finite, but all subgroups of $\Z$ infinite.


\begin{eg}
  (Non-example) Consider $D_6$ with $H = \bra s\ket$. $H$ is not a normal subgroup. We have $rH * r^2 H = r^3 H = H$, but $rH = rsH$ and $r^2H = srH$ (by considering the individual elements). So we have $rsH * srH = r^2 H\not= H$, and the operation is not well-defined.
\end{eg}

\begin{lemma}
  Given $K\lhd G$, the \emph{quotient map} $q: G\rightarrow G/K$ with $g\mapsto gK$ is a surjective group homomorphism.
\end{lemma}

\begin{proof}
  $q(ab) = (ab)K = aKbK = q(a)q(b)$. So $q$ is a group homomorphism. Also for all $aK \in G/K$, $q(a) = aK$. So it is surjective.
\end{proof}
Note that the kernel of the quotient map is $K$ itself. So any normal subgroup is a kernel of some homomorphism.

\begin{prop}
  The quotient of a cyclic group is cyclic.
\end{prop}

\begin{proof}
  Let $G = C_n$ with $H\leq C_n$. We know that $H$ is also cyclic. Say $C_n = \bra c\ket$ and $H = \bra c^k \ket \cong C_\ell$, where $k\ell = n$. We have $C_n/H = \{H, cH, c^2H, \cdots c^{k - 1}H\}=\bra cH\ket \cong C_k$.
\end{proof}

\subsection{The Isomorphism Theorem}
Now we come to the Really Important Theorem\textsuperscript{TM}.
\begin{thm}[The Isomorphism Theorem]
  Let $f:G\to H$ be a group homomorphism with kernel $K$. Then $K\lhd G$ and $G/K\cong \im f$.
\end{thm}

\begin{proof}
  We have proved that $K\lhd G$ before. We define a group homomorphism $\theta: G/K\to \im f$ by $\theta(aK) = f(a)$.

  First check that this is well-defined: If $a_1K = a_2K$, then $a_2^{-1}a_1\in K$. So
  \[
    f(a_2)^{-1}f(a_1) = f(a_2^{-1}a_1) = e.
  \]
  So $f(a_1) = f(a_2)$ and $\theta(a_1K) = \theta(a_2 K)$.

  Now we check that it is a group homomorphism:
  \[
    \theta(aKbK) = \theta(abK) = f(ab) = f(a)f(b) = \theta(aK) \theta(bK).
  \]
  To show that it is injective, suppose $\theta(aK) = \theta(bK)$. Then $f(a) = f(b)$. Hence $f(b)^{-1}f(a) = e$. Hence $b^{-1}a \in K$. So $aK = bK$.

  By definition, $\theta$ is surjective since $\im \theta = \im f$. So $\theta$ gives an isomorphism $G/K \cong \im f \leq H$.
\end{proof}
If $f$ is injective, then the kernel is $\{e\}$, so $G/K\cong G$ and $G$ is isomorphic to a subgroup of $H$. We can think of $f$ as an inclusion map. If $f$ is surjective, then $\im f = H$. In this case, $G/K \cong H$.

\begin{eg}\leavevmode
  \begin{enumerate}
    \item Take $f: \GL_n(\R) \to \R^*$ with $A \mapsto \det A$, $\ker f = \SL_N(\R)$. $\im f = \R^*$ as for all $\lambda \in \R^*$, $\det
      \begin{pmatrix}
        \lambda & 0 & \cdots & 0 \\
        0 &1 & \cdots & 0\\
        \vdots &\vdots &\ddots & \vdots\\
        0& 0 & 0 &1
      \end{pmatrix}
      = \lambda$. So we know that $\GL_n(\R)/\SL_n(\R) \cong \R^*$.
    \item Define $\theta: (\R, +) \to (\C*, \times)$ with $r\mapsto \exp(2\pi ir)$. This is a group homomorphism since $\theta(r + s) = \exp(2\pi i(r + s)) = \exp (2\pi i r)\exp (2\pi i s) = \theta(r)\theta(s)$. We know that the kernel is $\Z\lhd \R$. Clearly the image is the unit circle $(S_1, \times)$. So $\R/\Z \cong (S_1, \times)$.
    \item $G = (\Z_p^*, \times)$ for prime $p\not= 2$. We have $f: G\to G$ with $a\mapsto a^2$. This is a homomorphism since $(ab)^2 = a^2b^2$ ($\Z_p^*$ is abelian). The kernel is $\{\pm 1\} = \{1, p - 1\}$. We know that $\im f\cong G/\ker f$ with order $\frac{p - 1}{2}$. These are known as quadratic residues.
  \end{enumerate}
\end{eg}

\begin{lemma}
  Any cyclic group is isomorphic to either $\Z$ or $\Z/(n\Z)$ for some $n\in \N$.
\end{lemma}

\begin{proof}
  Let $G = \bra c\ket$. Define $f: \Z \to G$ with $m\mapsto c^m$. This is a group homomorphism since $c^{m_1 + m_2} = c^{m_1}c^{m_2}$. $f$ is surjective since $G$ is by definition all $c^m$ for all $m$. We know that $\ker f\lhd \Z$. We have three possibilities. Either
  \begin{enumerate}
    \item $\ker f = \{e\}$, so $F$ is an isomorphism and $G\cong \Z$; or
    \item $\ker f = \Z$, then $G\cong \Z/\Z = \{e\} = C_1$; or
    \item $\ker f = n\Z$ (since these are the only proper subgroups of $\Z$), then $G\cong \Z/(n\Z)$.\qedhere
  \end{enumerate}
\end{proof}

\begin{defi}[Simple group]
  A group is \emph{simple} if it has no non-trivial proper normal subgroup, i.e.\ only $\{e\}$ and $G$ are normal subgroups.
\end{defi}

\begin{eg}
  $C_p$ for prime $p$ are simple groups since it has no proper subgroups at all, let alone normal ones.
  $A_5$ is simple, which we will prove after Chapter~\ref{sec:sym2}.
\end{eg}

The finite simple groups are the building blocks of all finite groups. All finite simple groups have been classified (The Atlas of Finite Groups). If we have $K\lhd G$ with $K\not= G$ or $\{e\}$, then we can ``quotient out'' $G$ into $G/K$. If $G/K$ is not simple, repeat. Then we can write $G$ as an ``inverse quotient'' of simple groups.

\section{Group actions}
\label{sec:action}
Recall that we came up with groups to model symmetries and permutations. Intuitively, elements of groups are supposed to ``do things''. However, as we developed group theory, we abstracted these away and just looked at how elements combine to form new elements. \emph{Group actions} recapture this idea and make each group element correspond to some function.

\subsection{Group acting on sets}
\begin{defi}[Group action]
  Let $X$ be a set and $G$ be a group. An \emph{action} of $G$ on $X$ is a homomorphism $\varphi: G \to \Sym X$.
\end{defi}
This means that the homomorphism $\varphi$ turns each element $g\in G$ into a permutation of $X$, in a way that respects the group structure.

Instead of writing $\varphi(g)(x)$, we usually directly write $g(x)$ or $gx$.

Alternatively, we can define the group action as follows:
\begin{prop}
  Let $X$ be a set and $G$ be a group. Then $\varphi: G \to \Sym X$ is a homomorphism (i.e.\ an action) iff $\theta: G\times X \to X$ defined by $\theta(g, x) = \varphi(g)(x)$ satisfies
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item $(\forall g\in G)(x\in X)\,\theta(g, x)\in X$.
    \item $(\forall x\in X)\,\theta(e, x) = x$.
    \item $(\forall g, h\in G)(\forall x\in X)\,\theta(g, \theta (h, x)) = \theta(gh, x)$.
  \end{enumerate}
\end{prop}
This criteria is \emph{almost} the definition of a homomorphism. However, here we do not explicitly require $\theta(g, \cdot)$ to be a bijection, but require $\theta(e, \cdot)$ to be the identity function. This automatically ensures that $\theta(g, \cdot)$ is a bijection, since when composed with $\theta(g^{-1}, \cdot)$, it gives $\theta(e, \cdot)$, which is the identity. So $\theta(g, \cdot)$ has an inverse. This is usually an easier thing to show.

\begin{eg}\leavevmode
  \begin{enumerate}
    \item Trivial action: for any group $G$ acting on any set $X$, we can have $\varphi(g) = 1_X$ for all $g$, i.e.\ $G$ does nothing.
    \item $S_n$ acts on $\{1, \cdots n\}$ by permutation.
    \item $D_{2n}$ acts on the vertices of a regular $n$-gon (or the set $\{1, \cdots, n\}$).
    \item The rotations of a cube act on the faces/vertices/diagonals/axes of the cube.
  \end{enumerate}
\end{eg}
Note that different groups can act on the same sets, and the same group can act on different sets.

\begin{defi}[Kernel of action]
  The \emph{kernel} of an action $G$ on $X$ is the kernel of $\varphi$, i.e.\ all $g$ such that $\varphi(g) = 1_X$.
\end{defi}
Note that by the isomorphism theorem, $\ker \varphi\lhd G$ and $G/K$ is isomorphic to a subgroup of $\Sym X$.

\begin{eg}\leavevmode
  \begin{enumerate}
    \item $D_{2n}$ acting on $\{1, 2\cdots n\}$ gives $\varphi: D_{2n}\to S_n$ with kernel $\{e\}$.
    \item Let $G$ be the rotations of a cube and let it act on the three axes $x, y, z$ through the faces. We have $\varphi: G\to S_3$. Then any rotation by $180^\circ$ doesn't change the axes, i.e.\ act as the identity. So the kernel of the action has at least 4 elements: $e$ and the three $180^\circ$ rotations. In fact, we'll see later that these 4 are exactly the kernel.
  \end{enumerate}
\end{eg}

\begin{defi}[Faithful action]
  An action is \emph{faithful} if the kernel is just $\{e\}$.
\end{defi}

\subsection{Orbits and Stabilizers}
\begin{defi}[Orbit of action]
  Given an action $G$ on $X$, the \emph{orbit} of an element $x\in X$ is
  \[
    \orb (x) = G(x) = \{y\in X: (\exists g\in G)\,g(x) = y\}.
  \]
  Intuitively, it is the elements that $x$ can possibly get mapped to.
\end{defi}
\begin{defi}[Stabilizer of action]
  The \emph{stabilizer} of $x$ is
  \[
    \stab(x) = G_x = \{g\in G: g(x) = x\}\subseteq G.
  \]
  Intuitively, it is the elements in $G$ that do not change $x$.
\end{defi}

\begin{lemma}
  $\stab(x)$ is a subgroup of $G$.
\end{lemma}

\begin{proof}
  We know that $e(x) = x$ by definition. So $\stab(x)$ is non-empty. Suppose $g, h\in \stab(x)$, then $gh^{-1}(x) = g(h^{-1}(x)) = g(x) = x$. So $gh^{-1}\in \stab (X)$. So $\stab (x)$ is a subgroup.
\end{proof}

\begin{eg}\leavevmode
  \begin{enumerate}
    \item Consider $D_8$ acting on the corners of the square $X = \{1, 2, 3, 4\}$. Then $\orb(1) = X$ since $1$ can go anywhere by rotations. $\stab(1) = \{e, $ reflection in the line through 1$\}$
    \item Consider the rotations of a cube acting on the three axes $x, y, z$. Then $\orb(x)$ is everything, and $\stab(x)$ contains $e$, $180^\circ$ rotations and rotations about the $x$ axis.
  \end{enumerate}
\end{eg}

\begin{defi}[Transitive action]
  An action $G$ on $X$ is \emph{transitive} if $(\forall x)\,\orb(x) = X$, i.e.\ you can reach any element from any element.
\end{defi}

\begin{lemma}
  The orbits of an action partition $X$.
\end{lemma}

\begin{proof}
  Firstly, $(\forall x)(x\in \orb (x))$ as $e(x) = x$. So every $x$ is in some orbit.

  Then suppose $z\in \orb (x)$ and $z\in \orb (y)$, we have to show that $\orb(x) = \orb (y)$. We know that $z = g_1(x)$ and $z = g_2(y)$ for some $g_1, g_2$. Then $g_1(x) = g_2(y)$ and $y = g_2^{-1}g_1(x)$.

  For any $w = g_3(y)\in \orb (y)$, we have $w = g_3g_2^{-1}g_1(x)$. So $w\in \orb (x)$. Thus $\orb (y) \subseteq \orb (x)$ and similarly $\orb (x) \subseteq \orb (y)$. Therefore $\orb (x) = \orb (y)$.
\end{proof}

Suppose a group $G$ acts on $X$. We fix an $x \in X$. Then by definition of the orbit, given any $g \in G$, we have $g(x) \in \orb(x)$. So each $g \in G$ gives us a member of $\orb(x)$. Conversely, every object in $\orb(x)$ arises this way, by definition of $\orb(x)$. However, different elements in $G$ can give us the same orbit. In particular, if $g \in \stab(x)$, then $hg$ and $h$ give us the same object in $\orb(x)$, since $hg(x) = h(g(x)) = h(x)$. So we have a correspondence between things in $\orb(x)$ and members of $G$, ``up to $\stab (x)$''.

\begin{thm}[Orbit-stabilizer theorem]
  Let the group $G$ act on $X$. Then there is a bijection between $\orb(x)$ and cosets of $\stab(x)$ in $G$. In particular, if $G$ is finite, then
  \[
    |\orb(x)||\stab(x)| = |G|.
  \]
\end{thm}

\begin{proof}
  We biject the cosets of $\stab(x)$ with elements in the orbit of $x$. Recall that $G: \stab(x)$ is the set of cosets of $\stab(x)$. We can define
  \begin{align*}
    \theta: (G:\stab(x))& \to \orb(x)\\
    g\stab(x) &\mapsto g(x).
  \end{align*}
  This is well-defined --- if $g\stab(x) = h\stab(x)$, then $h = gk$ for some $k\in \stab(x)$. So $h(x) = g(k(x)) = g(x)$.

  This map is surjective since for any $y\in \orb(x)$, there is some $g \in G$ such that $g(x) = y$, by definition. Then $\theta(g \stab(x)) = y$. It is injective since if $g(x) = h(x)$, then $h^{-1}g(x) = x$. So $h^{-1}g\in \stab (x)$. So $g\stab(x) = h\stab(x)$.

  Hence the number of cosets is $|\orb(x)|$. Then the result follows from Lagrange's theorem.
\end{proof}
An important application of the orbit-stabilizer theorem is determining group sizes. To find the order of the symmetry group of, say, a pyramid, we find something for it to act on, pick a favorite element, and find the orbit and stabilizer sizes.

\begin{eg}\leavevmode
  \begin{enumerate}
    \item Suppose we want to know how big $D_{2n}$ is. $D_{2n}$ acts on the vertices $\{1, 2, 3, \cdots, n\}$ transitively. So $|\orb(1)| = n$. Also, $\stab(1) =\{e, $ reflection in the line through 1$\}$. So $|D_{2n}| = |\orb(1)||\stab(1)| = 2n$.

      Note that if the action is transitive, then all orbits have size $|X|$ and thus all stabilizers have the same size.
    \item Let $\bra (1\; 2)\ket$ act on $\{1, 2, 3\}$. Then $\orb(1) = \{1, 2\}$ and $\stab(1) = \{e\}$. $\orb(3) = \{3\}$ and $\stab(3) = \bra(1\; 2)\ket$.
    \item Consider $S_4$ acting on $\{1, 2, 3, 4\}$. We know that $\orb(1) = X$ and $|S_4| = 24$. So $|\stab(1)| = \frac{24}{4} = 6$. That makes it easier to find $\stab(1)$. Clearly $S_{\{2, 3, 4\}} \cong S_3$ fix $1$. So $S_{\{2, 3, 4\}}\leq \stab(1)$. However, $|S_3| = 6 = |\stab(1)|$, so this is all of the stabilizer.
  \end{enumerate}
\end{eg}

\subsection{Important actions}
Given any group $G$, there are a few important actions we can define. In particular, we will define the \emph{conjugation} action, which is a very important concept on its own. In fact, the whole of the next chapter will be devoted to studying conjugation in the symmetric groups.

First, we will study some less important examples of actions.
\begin{lemma}[Left regular action]
  Any group $G$ acts on itself by left multiplication. This action is faithful and transitive.
\end{lemma}
\begin{proof}
  We have
  \begin{enumerate}[label=\arabic{*}.]
    \item $(\forall g\in G)(x\in G)\,g(x) = g\cdot x \in G$ by definition of a group.
    \item $(\forall x\in G)\,e\cdot x = x$ by definition of a group.
    \item $g(hx) = (gh)x$ by associativity.
  \end{enumerate}
  So it is an action.

  To show that it is faithful, we want to know that $[(\forall x\in X)\,gx = x]\Rightarrow g = e$. This follows directly from the uniqueness of identity.

  To show that it is transitive, $\forall x, y\in G$, then $(yx^{-1})(x) = y$. So any $x$ can be sent to any $y$.
\end{proof}

\begin{thm}[Cayley's theorem]
  Every group is isomorphic to some subgroup of some symmetric group.
\end{thm}

\begin{proof}
  Take the left regular action of $G$ on itself. This gives a group homomorphism $\varphi: G\to \Sym G$ with $\ker \varphi = \{e\}$ as the action is faithful. By the isomorphism theorem, $G \cong \im \varphi \leq \Sym G$.
\end{proof}

\begin{lemma}[Left coset action]
  Let $H\leq G$. Then $G$ acts on the left cosets of $H$ by left multiplication transitively.
\end{lemma}

\begin{proof}
  First show that it is an action:
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item $g(aH) = (ga)H$ is a coset of $H$.
    \item $e(aH) = (ea)H = aH$.
    \item $g_1(g_2(aH)) = g_1((g_2a)H) = (g_1g_2a)H = (g_1g_2)(aH)$.
  \end{enumerate}

  To show that it is transitive, given $aH, bH$, we know that $(ba^{-1})(aH) = bH$. So any $aH$ can be mapped to $bH$.
\end{proof}
In the boring case where $H = \{e\}$, then this is just the left regular action since $G/\{e\} \cong G$.

\begin{defi}[Conjugation of element]
  The \emph{conjugation} of $a\in G$ by $b\in G$ is given by $bab^{-1}\in G$. Given any $a, c$, if there exists some $b$ such that $c = bab^{-1}$, then we say $a$ and $c$ are \emph{conjugate}.
\end{defi}
What is conjugation? This $bab^{-1}$ form looks familiar from Vectors and Matrices. It is the formula used for changing basis. If $b$ is the change-of-basis matrix and $a$ is a matrix, then the matrix in the new basis is given by $bab^{-1}$. In this case, $bab^{-1}$ is the same matrix viewed from a different basis.

In general, two conjugate elements are ``the same'' in some sense. For example, we will later show that in $S_n$, two elements are conjugate if and only if they have the same cycle type. Conjugate elements in general have many properties in common, such as their order.

\begin{lemma}[Conjugation action]
  Any group $G$ acts on itself by conjugation (i.e.\ $g(x) = gxg^{-1}$).
\end{lemma}

\begin{proof}
  To show that this is an action, we have
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item $g(x) = gxg^{-1} \in G$ for all $g, x\in G$.
    \item $e(x) = exe^{-1} = x$
    \item $g(h(x)) = g(hxh^{-1}) = ghxh^{-1}g^{-1} = (gh)x(gh)^{-1} = (gh)(x)$\qedhere
  \end{enumerate}
\end{proof}

\begin{defi}[Conjugacy classes and centralizers]
  The \emph{conjugacy classes} are the orbits of the conjugacy action.
  \[
    \ccl(a) = \{b\in G: (\exists g\in g)\,gag^{-1} = b\}.
  \]
  The \emph{centralizers} are the stabilizers of this action, i.e.\ elements that commute with $a$.
  \[
    C_G(a) = \{g\in G: gag^{-1} = a\} = \{g\in G: ga = ag\}.
  \]
\end{defi}
The centralizer is defined as the elements that commute with a particular element $a$. For the whole group $G$, we can define the \emph{center}.

\begin{defi}[Center of group]
  The \emph{center} of $G$ is the elements that commute with all other elements.
  \[
    Z(G) = \{g\in G: (\forall a)\,gag^{-1} = a\} = \{g\in G: (\forall a)\,ga = ag\}.
  \]
  It is sometimes written as $C(G)$ instead of $Z(G)$.
\end{defi}

In many ways, conjugation is related to normal subgroups.
\begin{lemma}
  Let $K\lhd G$. Then $G$ acts by conjugation on $K$.
\end{lemma}

\begin{proof}
  We only have to prove closure as the other properties follow from the conjugation action. However, by definition of a normal subgroup, for every $g \in G, k \in K$, we have $gkg^{-1}\in K$. So it is closed.
\end{proof}

\begin{prop}
  Normal subgroups are exactly those subgroups which are unions of conjugacy classes.
\end{prop}

\begin{proof}
  Let $K\lhd G$. If $k\in K$, then by definition for every $g \in G$, we get $gkg^{-1}\in K$. So $\ccl(k)\subseteq K$. So $K$ is the union of the conjugacy classes of all its elements.

  Conversely, if $K$ is a union of conjugacy classes and a subgroup of $G$, then for all $k \in K, g \in G$, we have $gkg^{-1}\in K$. So $K$ is normal.
\end{proof}

\begin{lemma}
  Let $X$ be the set of subgroups of $G$. Then $G$ acts by conjugation on $X$.
\end{lemma}

\begin{proof}
  To show that it is an action, we have
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item If $H\leq G$, then we have to show that $gHg^{-1}$ is also a subgroup. We know that $e\in H$ and thus $geg^{-1} = e\in gHg^{-1}$, so $gHg^{-1}$ is non-empty. For any two elements $gag^{-1}$ and $gbg^{-1}\in gHg^{-1}$, $(gag^{-1})(gbg^{-1})^{-1} = g(ab^{-1})g^{-1}\in gHg^{-1}$. So $gHg^{-1}$ is a subgroup.
    \item $eHe^{-1} = H$.
    \item $g_1(g_2Hg_2^{-1})g_1^{-1} = (g_1g_2)H(g_1g_2)^{-1}$.\qedhere
  \end{enumerate}
\end{proof}
Under this action, normal subgroups have singleton orbits.

\begin{defi}[Normalizer of subgroup]
  The \emph{normalizer} of a subgroup is the stabilizer of the (group) conjugation action.
  \[
    N_G(H) = \{g\in G: gHg^{-1} = H\}.
  \]
\end{defi}
We clearly have $H\subseteq N_G(H)$. It is easy to show that $N_G(H)$ is the largest subgroup of $G$ in which $H$ is a normal subgroup, hence the name.

There is a connection between actions in general and conjugation of subgroups.

\begin{lemma}
  Stabilizers of the elements in the same orbit are conjugate, i.e.\ let $G$ act on $X$ and let $g\in G, x\in X$. Then $\stab(g(x)) = g\stab(x)g^{-1}$.
\end{lemma}

\subsection{Applications}
\begin{eg}
  Let $G^{+}$ be the rotations of a cube acting on the vertices. Let $X$ be the set of vertices. Then $|X| = 8$. Since the action is transitive, the orbit of element is the whole of $X$. The stabilizer of vertex $1$ is the set of rotations through $1$ and the diagonally opposite vertex, of which there are 3. So $|G^{+}| = |\orb(1)||\stab(1)| = 8\cdot 3 = 24$.
\end{eg}

\begin{eg}
  Let $G$ be a finite simple group of order greater than 2, and $H\leq G$ have index $n\not= 1$. Then $|G| \leq n!/2$.
\end{eg}

\begin{proof}
  Consider the left coset action of $G$ on $H$. We get a group homomorphism $\varphi: G\to S_n$ since there are $n$ cosets of $H$. Since $H\not= G$, $\varphi$ is non-trivial and $\ker \varphi \not=G$. Now $\ker \varphi \lhd G$. Since $G$ is simple, $\ker\varphi = \{e\}$. So $G\cong \im \varphi \subseteq S_n$ by the isomorphism theorem. So $|G| \leq |S_n| = n!$.

  We can further refine this by considering $\sgn\circ \varphi: G \to \{\pm 1\}$. The kernel of this composite is normal in $G$. So $K = \ker(\sgn\circ\phi) = \{e\}$ or $G$. Since $G/K\cong \im (\sgn\circ\phi)$, we know that $|G|/|K| = 1$ or $2$ since $\im(\sgn\circ \phi)$ has at most two elements. Hence for $|G|> 2$, we cannot have $K = \{e\}$, or else $|G|/|K| > 2$. So we must have $K = G$, so $\sgn(\varphi(g)) = 1$ for all $g$ and $\im \varphi \leq A_n$. So $|G|\leq n!/2$
\end{proof}

We have seen on Sheet 1 that if $|G|$ is even, then $G$ has an element of order 2. In fact,
\begin{thm}[Cauchy's Theorem]
  Let $G$ be a finite group and prime $p$ dividing $|G|$. Then $G$ has an element of order $p$ (in fact there must be at least $p - 1$ elements of order $p$).
\end{thm}
It is important to remember that this only holds for prime $p$. For example, $A_4$ doesn't have an element of order $6$ even though $6 \mid 12 = |A_4|$. The converse, however, holds for any number trivially by Lagrange's theorem.

\begin{proof}
  Let $G$ and $p$ be fixed. Consider $G^p = G\times G\times \cdots \times G$, the set of $p$-tuples of $G$. Let $X \subseteq G^p$ be $X = \{(a_1, a_2, \cdots, a_p)\in G^p: a_1a_2\cdots a_p = e\}$.

  In particular, if an element $b$ has order $p$, then $(b, b, \cdots, b)\in X$. In fact, if $(b, b, \cdots, b)\in X$ and $b\not= e$, then $b$ has order $p$, since $p$ is prime.

  Now let $H = \bra h: h^p = e\ket\cong C_p$ be a cyclic group of order $p$ with generator $h$ (This $h$ is not related to $G$ in any way). Let $H$ act on $X$ by ``rotation'':
  \[
    h(a_1, a_2, \cdots, a_p) = (a_2, a_3, \cdots, a_p, a_1)
  \]
  This is an action:
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item If $a_1\cdots a_p = e$, then $a_1^{-1} = a_2\cdots a_p$. So $a_2\cdots a_pa_1 = a_1^{-1}a_1 = e$. So $(a_2, a_3, \cdots, a_p, a_1)\in X$.
    \item $e$ acts as an identity by construction
    \item The ``associativity'' condition also works by construction.
  \end{enumerate}

  As orbits partition $X$, the sum of all orbit sizes must be $|X|$. We know that $|X| = |G|^{p - 1}$ since we can freely choose the first $p - 1$ entries and the last one must be the inverse of their product. Since $p$ divides $|G|$, $p$ also divides $|X|$. We have $|\orb(a_1, \cdots , a_p)||\stab_H(a_1, \cdots, a_p)| = |H| = p$. So all orbits have size 1 or $p$, and they sum to $|X| = p\times$ something. We know that there is one orbit of size 1, namely $(e, e, \cdots, e)$. So there must be at least $p - 1$ other orbits of size 1 for the sum to be divisible by $p$.

  In order to have an orbit of size 1, they must look like ${(a, a, \cdots, a)}$ for some $a\in G$, which has order $p$.
\end{proof}

\section{Symmetric groups II}
\label{sec:sym2}
In this chapter, we will look at conjugacy classes of $S_n$ and $A_n$. It turns out this is easy for $S_n$, since two elements are conjugate if and only if they have the same cycle type. However, it is slightly more complicated in $A_n$. This is since while $(1\; 2\; 3)$ and $(1\; 3\; 2)$ might be conjugate in $S_4$, the element needed to perform the conjugation might be odd and not in $A_n$.

\subsection{Conjugacy classes in \texorpdfstring{$S_n$}{Sn}}
Recall $\sigma, \tau\in S_n$ are conjugate if $\exists \rho\in S_n$ such that $\rho \sigma\rho^{-1} = \tau$.

We first investigate the special case, when $\sigma$ is a $k$-cycle.
\begin{prop}
  If $(a_1\; a_2\; \cdots \; a_k)$ is a $k$-cycle and $\rho\in S_n$, then $\rho (a_1\; \cdots\; a_k)\rho^{-1}$ is the $k$-cycle $(\rho(a_1)\; \rho(a_2)\; \cdots \rho(a_3))$.
\end{prop}

\begin{proof}
  Consider any $\rho(a_1)$ acted on by $\rho (a_1\; \cdots\; a_k)\rho^{-1}$. The three permutations send it to $\rho(a_1)\mapsto a_1 \mapsto a_2 \mapsto \rho(a_2)$ and similarly for other $a_i$s. Since $\rho$ is bijective, any $b$ can be written as $\rho(a)$ for some $a$. So the result is the $k$-cycle $(\rho(a_1)\; \rho(a_2)\; \cdots \rho(a_3))$.
\end{proof}

\begin{cor}
  Two elements in $S_n$ are conjugate iff they have the same cycle type.
\end{cor}

\begin{proof}
  Suppose $\sigma = \sigma_1\sigma_2\cdots \sigma_\ell$, where $\sigma_i$ are disjoint cycles. Then $\rho\sigma\rho^{-1} = \rho\sigma_1\rho^{-1}\rho\sigma_2\rho^{-1}\cdots \rho\sigma_\ell\rho^{-1}$. Since the conjugation of a cycle conserves its length, $\rho\sigma\rho^{-1}$ has the same cycle type.

  Conversely, if $\sigma, \tau$ have the same cycle type, say
  \[
    \sigma = (a_1\; a_2\;\cdots\; a_k)(a_{k + 1}\; \cdots \;a_{k + \ell}),\quad \tau = (b_1\; b_2\;\cdots\; b_k)(b_{k + 1}\; \cdots \;b_{k + \ell}),
  \]
  if we let $\rho(a_i) = b_i$, then $\rho\sigma\rho^{-1} = \tau$.
\end{proof}

\begin{eg}
  Conjugacy classes of $S_4$:
  \begin{center}
    \begin{tabular}{lcccc}
      \toprule
      Cycle type & Example element & Size of ccl & Size of centralizer & Sign \\
      \midrule
      (1, 1, 1, 1) & e & 1 & 24 & $+1$ \\
      (2, 1, 1) & (1\; 2) & 6 & 4 & $-1$ \\
      (2, 2) & (1\; 2)(3\; 4) & 3 & 8 & $+1$ \\
      (3, 1) & (1\; 2\; 3) & 8 & 3 & $+1$ \\
      (4) & (1\; 2\; 3\; 4) & 6 & 4 & $-1$ \\
      \bottomrule
    \end{tabular}
  \end{center}

  \noindent We know that a normal subgroup is a union of conjugacy classes. We can now find all normal subgroups by finding possible union of conjugacy classes whose cardinality divides 24. Note that the normal subgroup must contain $e$.
  \begin{enumerate}
    \item Order 1: $\{e\}$
    \item Order 2: None
    \item Order 3: None
    \item Order 4: $\{e, (1\; 2)(3\; 4), (1\; 3)(2\; 4), (1\; 4)(2\; 3)\}\cong C_2\times C_2 = V_4$ is a possible candidate. We can check the group axioms and find that it is really a subgroup
    \item Order 6: None
    \item Order 8: None
    \item Order 12: $A_4$ (We know it is a normal subgroup since it is the kernel of the signature and/or it has index 2)
    \item Order 24: $S_4$
  \end{enumerate}
  We can also obtain the quotients of $S_4$: $S_4/\{e\} \cong S_4$, $S_4/V_4 \cong S_3\cong D_6$, $S_4/A_4 \cong C_2$, $S_4/S_4 = \{e\}$.
\end{eg}

\subsection{Conjugacy classes in \texorpdfstring{$A_n$}{An}}
We have seen that $|S_n| = 2|A_n|$ and that conjugacy classes in $S_n$ are ``nice''. How about in $A_n$?

The first thought is that we write it down:
\begin{align*}
  \ccl_{S_n}(\sigma) &= \{\tau\in S_n: (\exists \rho \in S_n)\, \tau = \rho\sigma\rho^{-1}\}\\
  \ccl_{A_n}(\sigma) &= \{\tau\in A_n: (\exists \rho \in A_n)\, \tau = \rho\sigma\rho^{-1}\}
\end{align*}
Obviously $\ccl_{A_n}(\sigma)\subseteq \ccl_{S_n}(\sigma)$, but the converse need not be true since the conjugation need to map $\sigma$ to $\tau$ may be odd.

\begin{eg}
  Consider $(1\; 2\; 3)$ and $(1\; 3\; 2)$. They are conjugate in $S_3$ by $(2\; 3)$, but $(2\; 3)\not\in A_3$. (This does not automatically entail that they are not conjugate in $A_3$ because there might be another even permutation that conjugate $(1\; 2\; 3)$ and $(1\; 3\; 2)$. In $A_5$, $(2\; 3)(4\; 5)$ works (but not in $A_3$))
\end{eg}

We can use the orbit-stabilizer theorem:
\begin{align*}
  |S_n| &= |\ccl_{S_n}(\sigma)||C_{S_n}(\sigma)|\\
  |A_n| &= |\ccl_{A_n}(\sigma)||C_{A_n}(\sigma)|
\end{align*}
We know that $A_n$ is half of $S_n$ and $\ccl_{A_n}$ is contained in $\ccl_{S_n}$. So we have two options: either $\ccl_{S_n}(\sigma) = \ccl_{A_n}(\sigma)$ and $|C_{S_n}(\sigma)| = \frac{1}{2}|C_{A_n}(\sigma)|$; or $\frac{1}{2}|\ccl_{S_n}(\sigma)| = |\ccl_{A_n}(\sigma)|$ and $C_{A_n}(\sigma) = C_{S_n}(\sigma)$.

\begin{defi}[Splitting of conjugacy classes]
  When $|\ccl_{A_n}(\sigma)| = \frac{1}{2}|\ccl_{S_n}(\sigma)|$, we say that the conjugacy class of $\sigma$ \emph{splits} in $A_n$.
\end{defi}

So the conjugacy classes are either retained or split.

\begin{prop}
  For $\sigma\in A_n$, the conjugacy class of $\sigma$ splits in $A_n$ if and only if no odd permutation commutes with $\sigma$.
\end{prop}

\begin{proof}
  We have the conjugacy classes splitting if and only if the centralizer does not. So instead we check whether the centralizer splits. Clearly $C_{A_n}(\sigma) = C_{S_n}(\sigma)\cap A_n$. So splitting of centralizer occurs if and only if an odd permutation commutes with $\sigma$.
\end{proof}

\begin{eg}
  Conjugacy classes in $A_4$:
  \begin{center}
    \begin{tabular}{lcccc}
      \toprule
      Cycle type & Example & $|\ccl_{S_4}|$ & Odd element in $C_{S_4}$? & $|\ccl_{A_4}|$ \\
      \midrule
      (1, 1, 1, 1) & $e$ & 1 & Yes $(1\; 2)$ & 1 \\
      (2, 2) & $(1\; 2)(3\; 4)$ & 3 & Yes $(1\; 2)$ & 3 \\
      (3, 1) & $(1\; 2\; 3)$ & 8 & No & 4, 4 \\
      \bottomrule
    \end{tabular}
  \end{center}
  In the (3, 1) case, by the orbit stabilizer theorem, $|C_{S_4}((1\; 2\; 3))| = 3$, which is odd and cannot split.
\end{eg}

\begin{eg}
  Conjugacy classes in $A_5$:
  \begin{center}
    \begin{tabular}{lcccc}
      \toprule
      Cycle type & Example & $|\ccl_{S_5}|$ & Odd element in $C_{S_5}$? & $|\ccl_{A_5}|$ \\
      \midrule
      (1, 1, 1, 1, 1) & $e$ & 1 & Yes $(1\; 2)$ & 1 \\
      (2, 2, 1) & $(1\; 2)(3\; 4)$ & 15 & Yes $(1\; 2)$ & 15 \\
      (3, 1, 1) & $(1\; 2\; 3)$ & 20 & Yes $(4\; 5)$ & 20 \\
      (5) & $(1\; 2\; 3\; 4\; 5)$ & 24 & No & 12, 12 \\
      \bottomrule
    \end{tabular}
  \end{center}
  Since the centralizer of $(1\; 2\; 3\; 4\; 5)$ has size $5$, it cannot split, so its conjugacy class must split.
\end{eg}

\begin{lemma}
  $\sigma = (1\; 2\; 3\; 4\; 5)\in S_5$ has $C_{S_5}(\sigma) = \bra \sigma \ket$. \end{lemma}

\begin{proof}
  $|\ccl_{S_n}(\sigma)| = 24$ and $|S_5| = 120$. So $|C_{S_5}(\sigma)| = 5$. Clearly $\bra \sigma \ket \subseteq C_{S_5}(\sigma)$. Since they both have size $5$, we know that $C_{S_5}(\sigma) = \bra \sigma\ket$
\end{proof}

\begin{thm}
  $A_5$ is simple.
\end{thm}

\begin{proof}
  We know that normal subgroups must be unions of the conjugacy classes, must contain $e$ and their order must divide 60. The possible orders are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30. However, the conjugacy classes 1, 15, 20, 12, 12 cannot add up to any of the possible orders apart from 1 and 60. So we only have trivial normal subgroups.
\end{proof}
In fact, all $A_n$ for $n\geq 5$ are simple, but the proof is horrible (cf.\ IB Groups, Rings and Modules).

\section{Quaternions}
In the remaining of the course, we will look at different important groups. Here, we will have a brief look at
\begin{defi}[Quaternions]
  The \emph{quaternions} is the set of matrices
  \begin{gather*}
    \begin{pmatrix}
      1&0\\0&1
    \end{pmatrix},
    \begin{pmatrix}
      i & 0\\0&-i
    \end{pmatrix},
    \begin{pmatrix}
      0&1\\-1&0
    \end{pmatrix},
    \begin{pmatrix}
      0&i\\i&0
    \end{pmatrix}
    \\
    \begin{pmatrix}
      -1&0\\0&-1
    \end{pmatrix},
    \begin{pmatrix}
      -i & 0\\0&i
    \end{pmatrix},
    \begin{pmatrix}
      0&-1\\1&0
    \end{pmatrix},
    \begin{pmatrix}
      0&-i\\-i&0
    \end{pmatrix}
  \end{gather*}
  which is a subgroup of $\GL_2(\C)$.
\end{defi}

\begin{notation}
  We can also write the quaternions as
  \[
    Q_8 = \bra a, b : a^4 = e, b^2 = a^2, bab^{-1} = a^{-1}\ket
  \]
  Even better, we can write
  \[
    Q_8 = \{1, -1, i, -i, j, -j, k, -k\}
  \]
  with
  \begin{enumerate}
    \item $(-1)^2 = 1$
    \item $i^2 = j^2 = k^2 = -1$
    \item $(-1)i = -i$ etc.
    \item $ij = k$, $jk = i$, $ki = j$
    \item $ji = -k$, $kj = -i$, $ik = -j$
  \end{enumerate}
  We have
  \begin{gather*}
    1 = \begin{pmatrix}
      1&0\\0&1
    \end{pmatrix},
    i = \begin{pmatrix}
      i & 0\\0&-i
    \end{pmatrix},
    j = \begin{pmatrix}
      0&1\\-1&0
    \end{pmatrix},
    k = \begin{pmatrix}
      0&i\\i&0
    \end{pmatrix}\\
    -1 = \begin{pmatrix}
      -1&0\\0&-1
    \end{pmatrix},
    -i = \begin{pmatrix}
      -i & 0\\0&i
    \end{pmatrix},
    -j = \begin{pmatrix}
      0&-1\\1&0
    \end{pmatrix},
    -k = \begin{pmatrix}
      0&-i\\-i&0
    \end{pmatrix}
  \end{gather*}
\end{notation}

\begin{lemma}
  If $G$ has order 8, then either $G$ is abelian (i.e.\ $\cong C_8, C_4\times C_2$ or $C_2\times C_2\times C_2$), or $G$ is not abelian and isomorphic to $D_8$ or $Q_8$ (dihedral or quaternion).
\end{lemma}

\begin{proof}
  Consider the different possible cases:
  \begin{itemize}
    \item If $G$ contains an element of order 8, then $G\cong C_8$.
    \item If all non-identity elements have order 2, then $G$ is abelian (Sheet 1, Q8). Let $a\not= b\in G\setminus\{e\}$. By the direct product theorem, $\bra a, b\ket = \bra a\ket\times\bra b\ket$. Then take $c\not\in \bra a, b\ket$. By the direct product theorem, we obtain $\bra a, b, c\ket = \bra a\ket\times\bra b\ket\times\bra c\ket = C_2\times C_2\times C_2$. Since $\bra a, b, c\ket\subseteq G$ and $|\bra a, b, c\ket| = |G|$, $G = \bra a, b, c\ket \cong C_2\times C_2\times C_2$.
    \item $G$ has no element of order 8 but has an order 4 element $a\in G$. Let $H = \bra a\ket$. Since $H$ has index 2, it is normal in $G$. So $G/H \cong C_2$ since $|G/H| = 2$. This means that for any $b\not\in H$, $bH$ generates $G/H$. Then $(bH)^2 = b^2H = H$. So $b^2\in H$. Since $b^2\in \bra a\ket$ and $\bra a\ket$ is a cyclic group, $b^2$ commutes with $a$.

      If $b^2 = a$ or $a^3$, then $b$ has order 8. Contradiction. So $b^2 = e$ or $a^2$.

      We also know that $H$ is normal, so $bab^{-1}\in H$. Let $bab^{-1} = a^\ell$. Since $a$ and $b^2$ commute, we know that $a = b^2 ab^{-2} = b(bab^{-1})b^{-1} = ba^\ell b^{-1} = (bab^{-1})^{\ell} = a^{\ell^2}$. So $\ell^2 \equiv 1\pmod 4$. So $\ell \equiv \pm 1 \pmod 4$.

      \begin{itemize}
        \item When $l\equiv 1\pmod 4$, $bab^{-1} = a$, i.e.\ $ba = ab$. So $G$ is abelian.
          \begin{itemize}
            \item If $b^2 = e$, then $G = \bra a, b\ket \cong \bra a\ket \times \bra b\ket \cong C_4\times C_2$.
            \item If $b^2 = a^2$, then $(ba^{-1})^2 = e$. So $G = \bra a, ba^{-1}\ket \cong C_4\times C_2$.
          \end{itemize}
        \item If $l \equiv -1\pmod 4$, then $bab^{-1} = a^{-1}$.
          \begin{itemize}
            \item If $b^2 = e$, then $G = \bra a, b: a^4 = e = b^2, bab^{-1} = a^{-1}\ket$. So $G\cong D_8$ by definition.
            \item If $b^2 = a^2$, then we have $G\cong Q_8$.\qedhere
          \end{itemize}
      \end{itemize}%\qedhere
  \end{itemize}
\end{proof}
\section{Matrix groups}
\subsection{General and special linear groups}
Consider $M_{n\times n}(F)$, i.e.\ the set of $n\times n$ matrices over the field $F = \R$ or $\C$ (or $\F_p$). We know that matrix multiplication is associative (since they represent functions) but are, in general, not commutative. To make this a group, we want the identity matrix $I$ to be the identity. To ensure everything has an inverse, we can only include invertible matrices.

(We do not necessarily need to take $I$ as the identity of the group. We can, for example, take $e =
\begin{pmatrix}
  0 & 0\\
  0 & 1
\end{pmatrix}$ and obtain a group in which every matrix is of the form $\begin{pmatrix}
  0 & 0\\
  0 & a
\end{pmatrix}$ for some non-zero $a$. This forms a group, albeit a boring one (it is simply $\cong \R^*$))
\begin{defi}[General linear group $\GL_n(F)$]
  \[
    \GL_n(F) = \{A\in M_{n\times n}(F) : A\text{ is invertible}\}
  \]
  is the \emph{general linear group}.
\end{defi}
Alternatively, we can define $\GL_n(F)$ as matrices with non-zero determinants.

\begin{prop}
  $\GL_n(F)$ is a group.
\end{prop}
\begin{proof}
  Identity is $I$, which is in $\GL_n(F)$ by definition ($I$ is its self-inverse). The composition of invertible matrices is invertible, so is closed. Inverse exist by definition. Multiplication is associative.
\end{proof}

\begin{prop}
  $\det: \GL_n(F) \to F\setminus\{0\}$ is a surjective group homomorphism.
\end{prop}

\begin{proof}
  $\det AB = \det A\det B$. If $A$ is invertible, it has non-zero determinant and $\det A\in F\setminus\{0\}$.

  To show it is surjective, for any $x\in F\setminus\{0\}$, if we take the identity matrix and replace $I_{11}$ with $x$, then the determinant is $x$. So it is surjective.
\end{proof}

\begin{defi}[Special linear group $\SL_n(F)$]
  The \emph{special linear group} $\SL_n(F)$ is the kernel of the determinant, i.e.
  \[
    SL_n(F) = \{A\in \GL_n(F): \det A = 1\}.
  \]
\end{defi}

So $\SL_n(F)\lhd \GL_n(F)$ as it is a kernel. Note that $Q_8\leq \SL_2(\C)$
\subsection{Actions of \texorpdfstring{$\GL_n(\C)$}{GLn(C)}}
\begin{prop}
  $\GL_n(\C)$ acts faithfully on $\C^n$ by left multiplication to the vector, with two orbits ($\mathbf{0}$ and everything else).
\end{prop}

\begin{proof}
  First show that it is a group action:
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{0}
    \item If $A\in \GL_n(\C)$ and $\mathbf{v}\in \C^n$, then $A\mathbf{v}\in \C^n$. So it is closed.
    \item $I\mathbf{v} = \mathbf{v}$ for all $\mathbf{v}\in \C^n$.
    \item $A(B\mathbf{v}) = (AB)\mathbf{v}$.
  \end{enumerate}

  Now prove that it is faithful: a linear map is determined by what it does on a basis. Take the standard basis $\mathbf{e}_1 = (1, 0, \cdots, 0), \cdots \mathbf{e}_n = (0, \cdots, 1)$. Any matrix which maps each $\mathbf{e}_k$ to itself must be $I$ (since the columns of a matrix are the images of the basis vectors)

  To show that there are 2 orbits, we know that $A\mathbf{0} = \mathbf{0}$ for all $A$. Also, as $A$ is invertible, $A\mathbf{v} = \mathbf{0}\Leftrightarrow \mathbf{v} = \mathbf{0}$. So $\mathbf{0}$ forms a singleton orbit. Then given any two vectors $\mathbf{v}\not= \mathbf{w}\in \C^n\setminus\{0\}$, there is a matrix $A\in \GL_n(\C)$ such that $A\mathbf{v} = \mathbf{w}$ (cf.\ Vectors and Matrices).
\end{proof}

Similarly, $\GL_n(\R)$ acts on $\R^n$.

\begin{prop}
  $\GL_n(\C)$ acts on $M_{n\times n}(\C)$ by conjugation. (Proof is trivial)
\end{prop}
This action can be thought of as a ``change of basis'' action. Two matrices are conjugate if they represent the same map but with respect to different bases. The $P$ is the base change matrix.

From Vectors and Matrices, we know that there are three different types of orbits for $\GL_2(\C)$: $A$ is conjugate to a matrix of one of these forms:
\begin{enumerate}
  \item $
    \begin{pmatrix}
      \lambda & 0\\
      0 & \mu
    \end{pmatrix}
    $, with $\lambda \not= \mu$, i.e.\ two distinct eigenvalues
  \item $
    \begin{pmatrix}
      \lambda & 0\\
      0 & \lambda\\
    \end{pmatrix}$, i.e.\ a repeated eigenvalue with 2-dimensional eigenspace
  \item $
    \begin{pmatrix}
      \lambda & 1\\
      0 & \lambda
    \end{pmatrix}$, i.e.\ a repeated eigenvalue with a 1-dimensional eigenspace
\end{enumerate}
Note that we said there are three \emph{types} of orbits, not three orbits. There are infinitely many orbits, e.g.\ one for each of $\lambda I$.
\subsection{Orthogonal groups}
Recall that $A^T$ is defined by $A^{T}_{ij} = A_{ji}$, i.e.\ we reflect the matrix in the diagonal. They have the following properties:
\begin{enumerate}
  \item $(AB)^T = B^TA^T$
  \item $(A^{-1})^T = (A^T)^{-1}$
  \item $A^{T}A = I\Leftrightarrow AA^{T} = I\Leftrightarrow A^{-1} = A^{T}$. In this case $A$ is \emph{orthogonal}
  \item $\det A^{T} = \det A$
\end{enumerate}
We are now in $\R$, because orthogonal matrices don't make sense with complex matrices.

Note that a matrix is orthogonal if the columns (or rows) form an orthonormal basis of $\R^n$: $AA^T = I\Leftrightarrow a_{ik}a_{jk} = \delta_{ij} \Leftrightarrow \mathbf{a}_i\cdot \mathbf{a}_j = \delta_{ij}$, where $\mathbf{a}_i$ is the $i$th column of $A$.

The importance of orthogonal matrices is that they are the isometries of $\R^n$.
\begin{lemma}[Orthogonal matrices are isometries] For any orthogonal $A$ and $x, y\in \R^n$, we have
  \begin{enumerate}
    \item $(A\mathbf{x})\cdot (A\mathbf{y}) = \mathbf{x\cdot y}$
    \item $|A\mathbf{x}| = |\mathbf{x}|$
  \end{enumerate}
\end{lemma}

\begin{proof}
  Treat the dot product as a matrix multiplication. So
  \[
    (A\mathbf{x})^T(A\mathbf{y}) = \mathbf{x}^{T}A^TAy = \mathbf{x}^TI\mathbf{y} = \mathbf{x}^T\mathbf{y}
  \]
  Then we have $|A\mathbf{x}|^2 = (A\mathbf{x})\cdot (A\mathbf{x}) = \mathbf{x}\cdot \mathbf{x} = |\mathbf{x}|^2$. Since both are positive, we know that $|A\mathbf{x}| = |\mathbf{x}|$.
\end{proof}
It is important to note that orthogonal matrices are isometries, but not all isometries are orthogonal. For example, translations are isometries but are not represented by orthogonal matrices, since they are not linear maps and cannot be represented by matrices at all! However, it is true that all linear isometries can be represented by orthogonal matrices.

\begin{defi}[Orthogonal group $O(n)$]
  The \emph{orthogonal group} is
  \[
    \Or(n) = \Or_n = \Or_n(\R) = \{A\in \GL_n(\R): A^TA = I\},
  \]
  i.e.\ the group of orthogonal matrices.
\end{defi}
We will later show that this is the set of matrices that preserve distances in $\R^n$.

\begin{lemma}
  The orthogonal group is a group.
\end{lemma}

\begin{proof}
  We have to check that it is a subgroup of $\GL_n(\R)$: It is non-empty, since $I\in \Or(n)$. If $A, B\in \Or(n)$, then $(AB^{-1})(AB^{-1})^T = AB^{-1}(B^{-1})^TA^{T} = AB^{-1}BA^{-1} = I$, so $AB^{-1}\in \Or(n)$ and this is indeed a subgroup.
\end{proof}


\begin{prop}
  $\det: \Or(n) \to \{\pm 1\}$ is a surjective group homomorphism.
\end{prop}

\begin{proof}
  For $A\in \Or(n)$, we know that $A^TA = I$. So $\det A^TA = (\det A)^2 = 1$. So $\det A = \pm 1$. Since $\det(AB) = \det A\det B$, it is a homomorphism. We have
  \[
    \det I = 1,\;\;\;\det
    \begin{pmatrix}
      -1 & 0 &\cdots & 0\\
      0 & 1 & \cdots & 0\\
      \vdots & \vdots & \ddots & 0\\
      0 & 0 & \cdots & 1
    \end{pmatrix} = -1,
  \]
  so it is surjective.
\end{proof}

\begin{defi}[Special orthogonal group $\SO(n)$]
  The \emph{special orthogonal group} is the kernel of $\det: \Or(n) \to \{\pm 1\}$.
  \[
    \SO(n) =\SO_n = \SO_n(\R) = \{A\in \Or(n): \det A = 1\}.
  \]
\end{defi}
By the isomorphism theorem, $\Or(n)/\SO(n) \cong C_2$.

What's wrong with matrices with determinant $-1$? Why do we want to eliminate these? An important example of an orthogonal matrix with determinant $-1$ is a \emph{reflection}. These transformations reverse orientation, and is often unwanted.

\begin{lemma}
  $\Or(n) = \SO(n) \cup
  \begin{pmatrix}
    -1 & 0 &\cdots & 0\\
    0 & 1 & \cdots & 0\\
    \vdots & \vdots & \ddots & 0\\
    0 & 0 & \cdots &1
  \end{pmatrix}\SO(n)$
\end{lemma}

\begin{proof}
  Cosets partition the group.
\end{proof}
\subsection{Rotations and reflections in \texorpdfstring{$\R^2$}{R2} and \texorpdfstring{$\R^3$}{R3}}
\begin{lemma}
  $\SO(2)$ consists of all rotations of $\R^2$ around 0.
\end{lemma}

\begin{proof}
  Let $A\in \SO(2)$. So $A^TA = I$ and $\det A = 1$. Suppose $A =
  \begin{pmatrix}
    a & b\\c & d
  \end{pmatrix}$. Then $A^{-1} =
  \begin{pmatrix}
    d & -b\\-c & a
  \end{pmatrix}.$ So $A^T = A^{-1}$ implies $ad - bc = 1$, $c = -b$, $d = a$. Combining these equations we obtain $a^2 + c^2 = 1$. Set $a = \cos\theta = d$, and $c = \sin\theta = -b$. Then these satisfies all three equations. So
  \[
    A =
    \begin{pmatrix}
      \cos\theta & -\sin\theta\\
      \sin\theta & \cos\theta
    \end{pmatrix}.
  \]
  Note that $A$ maps $(1, 0)$ to $(\cos\theta, \sin \theta)$, and maps $(0, 1)= (-\sin\theta, \cos\theta)$, which are rotations by $\theta$ counterclockwise. So $A$ represents a rotation by $\theta$.
\end{proof}

\begin{cor}
  Any matrix in $\Or(2)$ is either a rotation around $0$ or a reflection in a line through $0$.
\end{cor}

\begin{proof}
  If $A\in \SO(2)$, we've show that it is a rotation. Otherwise,
  \[
    A =
    \begin{pmatrix}
      1 & 0\\
      0 & -1
    \end{pmatrix}
    \begin{pmatrix}
      \cos\theta & -\sin\theta\\
      \sin\theta & \cos\theta
    \end{pmatrix} =
    \begin{pmatrix}
      \cos\theta & -\sin\theta \\
      -\sin\theta & -\cos\theta
    \end{pmatrix}
  \]
  since $\Or(2) = \SO(2)\cup
  \begin{pmatrix}
    1&0\\0&-1
  \end{pmatrix}\SO(2)$. This has eigenvalues $1, -1$. So it is a reflection in the line of the eigenspace $E_1$. The line goes through $\mathbf{0}$ since the eigenspace is a subspace which must include $\mathbf{0}$.
\end{proof}

\begin{lemma}
  Every matrix in $\SO(3)$ is a rotation around some axis.
\end{lemma}

\begin{proof}
  Let $A\in \SO(3)$. We know that $\det A = 1$ and $A$ is an isometry. The eigenvalues $\lambda$ must have $|\lambda| = 1$. They also multiply to $\det A = 1$. Since we are in $\R$, complex eigenvalues come in complex conjugate pairs. If there are complex eigenvalues $\lambda$ and $\bar\lambda$, then $\lambda\bar\lambda = |\lambda|^2 = 1$. The third eigenvalue must be real and has to be $+1$.

  If all eigenvalues are real. Then eigenvalues are either $1$ or $-1$, and must multiply to $1$. The possibilities are $1, 1, 1$ and $-1, -1, 1$, all of which contain an eigenvalue of $1$.

  So pick an eigenvector for our eigenvalue $1$ as the third basis vector. Then in some orthonormal basis,
  \[
    A = \begin{pmatrix}
      a & b & 0\\
      c & d & 0\\
      0 & 0 & 1
    \end{pmatrix}
  \]
  Since the third column is the image of the third basis vector, and by orthogonality the third row is $0, 0, 1$. Now let
  \[A' = \begin{pmatrix}
      a & b\\
      c & d
    \end{pmatrix} \in \GL_2(\R)
  \]
  with $\det A' = 1$. $A'$ is still orthogonal, so $A'\in \SO(2)$. Therefore $A'$ is a rotation and
  \[
    A =
    \begin{pmatrix}
      \cos\theta & -\sin\theta & 0\\
      \sin\theta & \cos\theta & 0\\
      0 & 0 & 1
    \end{pmatrix}
  \]
  in some basis, and this is exactly the rotation through an axis.
\end{proof}

\begin{lemma}
  Every matrix in $\Or(3)$ is the product of at most three reflections in planes through 0.
\end{lemma}
Note that a rotation is a product of two reflections. This lemma effectively states that every matrix in $\Or(3)$ is a reflection, a rotation or a product of a reflection and a rotation.

\begin{proof}
  Recall $\Or(3) = \SO(3) \cup
  \begin{pmatrix}
    1 & 0 & 0\\
    0 & 1 & 0\\
    0 & 0 & -1
  \end{pmatrix}SO(3)$.
  So if $A\in \SO(3)$, we know that $A =
  \begin{pmatrix}
    \cos\theta & -\sin\theta & 0\\
    \sin\theta & \cos\theta & 0\\
    0 & 0 & 1
  \end{pmatrix}$ in some basis, which is a composite of two reflections:
  \[
    A =
    \begin{pmatrix}
      1 & 0 & 0\\
      0 & -1 & 0\\
      0 & 0 & 1
    \end{pmatrix}
    \begin{pmatrix}
      \cos\theta & \sin\theta & 0\\
      \sin\theta & -\cos\theta & 0\\
      0 & 0 & 1
    \end{pmatrix},
  \]
  Then if $A\in \begin{pmatrix}
    1 & 0 & 0\\
    0 & 1 & 0\\
    0 & 0 & -1
  \end{pmatrix}\SO(3)$, then it is automatically a product of three reflections.
\end{proof}
In the last line we've shown that everything in $\Or(3)\setminus \SO(3)$ can be written as a product of three reflections, but it is possible that they need only 1 reflection. However, some matrices do genuinely need 3 reflections, e.g.
$\begin{pmatrix}
  -1 & 0 & 0\\
  0 & -1 & 0\\
  0 & 0 & -1
\end{pmatrix}$

\subsection{Unitary groups}
The concept of orthogonal matrices only make sense if we are talking about real matrices. If we are talking about complex, then instead we need \emph{unitary matrices}. To do so, we replace the transposition with the \emph{Hermitian conjugate}. It is defined by $A^\dagger = (A^*)^T$ with $(A^\dagger)_{ij} = A_{ji}^*$, where the asterisk is the complex conjugate. We still have
\begin{enumerate}
  \item $(AB)^\dagger = B^\dagger A^\dagger$
  \item $(A^{-1})^\dagger = (A^\dagger)^{-1}$
  \item $A^\dagger A = I \Leftrightarrow AA^\dagger = I \Leftrightarrow A^\dagger = A^{-1}$. We say $A$ is a \emph{unitary matrix}
  \item $\det A^{\dagger} = (\det A)^*$
\end{enumerate}

\begin{defi}[Unitary group $U(n)$]
  The \emph{unitary group} is
  \[
    \U(n) = \U_n = \{A\in \GL_n(\C): A^\dagger A = I\}.
  \]
\end{defi}

\begin{lemma}
  $\det: \U(n)\to S^1$, where $S^1$ is the unit circle in the complex plane, is a surjective group homomorphism.
\end{lemma}

\begin{proof}
  We know that $1 = \det I = \det A^\dagger A = |\det A|^2$. So $|\det A| = 1$. Since $\det AB = \det A\det B$, it is a group homomorphism.

  Now given $\lambda\in S_1$, we have
  $\begin{pmatrix}
    \lambda & 0 & \cdots & 0\\
    0 & 1 & \cdots & 0\\
    \vdots & \vdots & \ddots & 0\\
    0 & 0 & 0 & 1
  \end{pmatrix}\in \U(n)$. So it is surjective.
\end{proof}

\begin{defi}[Special unitary group $SU(n)$]
  The \emph{special unitary group} $\SU(n) = \SU_n$ is the kernel of $\det U(n)\to S^1$.
\end{defi}

Similarly, unitary matrices preserve the complex dot product: $(A\mathbf{x})\cdot (A\mathbf{y}) = \mathbf{x}\cdot \mathbf{y}$.

\section{More on regular polyhedra}
In this section, we will look at the symmetry groups of the cube and the tetrahedron.
\subsection{Symmetries of the cube}
\subsubsection*{Rotations}
Recall that there are $|G^+| = 24$ rotations of the group by the orbit-stabilizer theorem.
\begin{prop}
  $G^+ \cong S_4$, where $G^+$ is the group of all rotations of the cube.
\end{prop}

\begin{proof}
  Consider $G^+$ acting on the 4 diagonals of the cube. This gives a group homomorphism $\varphi: G^+ \to S_4$. We have $(1\; 2\; 3\; 4)\in\im \varphi$ by rotation around the axis through the top and bottom face. We also $(1\; 2)\in \im \varphi$ by rotation around the axis through the mid-point of the edge connect $1$ and $2$. Since $(1\; 2)$ and $(1\; 2\; 3\; 4)$ generate $S_4$ (Sheet 2 Q. 5d), $\im\varphi = S_4$, i.e.\ $\phi$ is surjective. Since $|S_4| = |G^+|$, $\varphi$ must be an isomorphism.
\end{proof}

\subsubsection*{All symmetries}
Consider the reflection in the mid-point of the cube $\tau$, sending every point to its opposite. We can view this as $-I$ in $\R^3$. So it commutes with all other symmetries of the cube.
\begin{prop}
  $G \cong S_4\times C_2$, where $G$ is the group of all symmetries of the cube.
\end{prop}

\begin{proof}
  Let $\tau$ be ``reflection in mid-point'' as shown above. This commutes with everything. (Actually it is enough to check that it commutes with rotations only)

  We have to show that $G = G^+\bra \tau\ket$. This can be deduced using sizes: since $G^+$ and $\bra\tau\ket$ intersect at $e$ only, (i) and (ii) of the Direct Product Theorem gives an injective group homomorphism $G^+\times \bra\tau\ket \to G$. Since both sides have the same size, the homomorphism must be surjective as well. So $G\cong G^+\times \bra \tau\ket \cong S_4\times C_2$.
\end{proof}

In fact, we have also proved that the group of symmetries of an octahedron is $S_4\times C_2$ since the octahedron is the dual of the cube. (if you join the centers of each face of the cube, you get an octahedron)
\begin{center}
  \begin{tikzpicture}[z = -5.5, scale = 1.5]
    \coordinate (O1) at (0, 0, -1);
    \coordinate (O2) at (-1, 0, 0);
    \coordinate (O3) at (0, 0, 1);
    \coordinate (O4) at (1, 0, 0);
    \coordinate (O5) at (0, 1, 0);
    \coordinate (O6) at (0, -1, 0);

    \draw [draw = blue, dashed] (O1) -- (O2) -- (O5) -- cycle;
    \draw [draw = blue, dashed] (O4) -- (O1) -- (O5) -- cycle;
    \draw [draw = blue, dashed] (O1) -- (O2) -- (O6) -- cycle;
    \draw [draw = blue, dashed] (O4) -- (O1) -- (O6) -- cycle;
    \draw [draw = blue] (O2) -- (O3) -- (O5) -- cycle;
    \draw [draw = blue] (O3) -- (O4) -- (O5) -- cycle;
    \draw [draw = blue] (O2) -- (O3) -- (O6) -- cycle;
    \draw [draw = blue] (O3) -- (O4) -- (O6) -- cycle;

    \coordinate (C1) at (-1, -1, -1);
    \coordinate (C2) at (-1, -1, 1);
    \coordinate (C3) at (-1, 1, 1);
    \coordinate (C4) at (-1, 1, -1);
    \coordinate (C5) at (1, -1, -1);
    \coordinate (C6) at (1, -1, 1);
    \coordinate (C7) at (1, 1, 1);
    \coordinate (C8) at (1, 1, -1);

    \draw [draw = red, dashed] (C1) -- (C2);
    \draw [draw = red] (C2) -- (C3);
    \draw [draw = red] (C3) -- (C4);
    \draw [draw = red, dashed] (C4) -- (C1);
    \draw [draw = red] (C5) -- (C6) -- (C7) -- (C8) -- cycle;
    \draw [draw = red, dashed] (C1) -- (C5);
    \draw [draw = red] (C2) -- (C6);
    \draw [draw = red] (C3) -- (C7);
    \draw [draw = red] (C4) -- (C8);
  \end{tikzpicture}
\end{center}

\subsection{Symmetries of the tetrahedron}
\subsubsection*{Rotations}
Let $1, 2, 3, 4$ be the vertices (in any order). $G^+$ is just the rotations. Let it act on the vertices. Then $\orb(1) = \{1, 2, 3, 4\}$ and $\stab(1) = \{$ rotations in the axis through 1 and the center of the opposite face $\} = \{e, \frac{2\pi}{3}, \frac{4\pi}{3}\}$

So $|G^+| = 4\cdot 3 = 12$ by the orbit-stabilizer theorem.

The action gives a group homomorphism $\varphi: G^+ \to S_4$. Clearly $\ker \varphi = \{e\}$. So $G^+ \leq S_4$ and $G^+$ has size 12. We ``guess'' it is $A_4$ (actually it \emph{must} be $A_4$ since that is the only subgroup of $S_4$ of order 12, but it's nice to see why that's the case).

If we rotate in an axis through 1, we get $(2\; 3\; 4), (2\; 4\; 3)$. Similarly, rotating through other axes through vertices gives all 3-cycles.

If we rotate through an axis that passes through two opposite edges, e.g.\ through 1-2 edge and 3-4 edge, then we have $(1\; 2)(3\; 4)$ and similarly we obtain all double transpositions. So $G^+ \cong A_4$. This shows that there is no \emph{rotation} that fixes two vertices and swaps the other two.

\subsubsection*{All symmetries}
Now consider the plane that goes through 1, 2 and the mid-point of 3 and 4. Reflection through this plane swaps 3 and 4, but doesn't change $1, 2$. So now $\stab(1) = \bra (2\; 3\; 4), (3, 4)\ket \cong D_6$ (alternatively, if we want to fix 1, we just move 2, 3, 4 around which is the symmetries of the triangular base)

So $|G| = 4\cdot 6 = 24$ and $G\cong S_4$ (which makes sense since we can move any of its vertices around in any way and still be a tetrahedron, so we have all permutations of vertices as the symmetry group)

\section{M\texorpdfstring{\"o}{o}bius group}
\subsection{M\texorpdfstring{\"o}{o}bius maps}
We want to study maps $f: \C \to \C$ in the form $f(z) = \frac{az + b}{cz + d}$ with $a, b, c, d\in \C$ and $ad - bc \not= 0$.

We impose $ad - bc\not= 0$ or else the map will be constant: for any $z, w\in \C$, $f(z) - f(w) = \frac{(az + b)(cw + d) - (aw + b)(cz + d)}{(cw + d)(cz + d)} = \frac{(ad - bc)(z - w)}{(cw + d)(cz + d)}$. If $ad - bc = 0$, then $f$ is constant and boring (more importantly, it will not be invertible).

If $c\not=0$, then $f(-\frac{d}{c})$ involves division by 0. So we add $\infty$ to $\C$ to form the extended complex plane (Riemann sphere) $\C\cup \{\infty\}= \C_\infty$ (cf.\ Vectors and Matrices). Then we define $f(-\frac{d}{c}) = \infty$. We call $\C_\infty$ a one-point compactification of $\C$ (because it adds one point to $\C$ to make it compact, cf.\ Metric and Topology).

\begin{defi}[M\"obius map]
  A \emph{M\"obius map} is a map from $\C_\infty \to \C_\infty$ of the form
  \[
    f(z) = \frac{az + b}{cz + d},
  \]
  where $a, b, c, d\in \C$ and $ad - bc\not= 0$, with $f(-\frac{d}{c}) = \infty$ and $f(\infty) = \frac{a}{c}$ when $c\not= 0$. (if $c = 0$, then $f(\infty)=\infty$)
\end{defi}

\begin{lemma}
  The M\"obius maps are bijections $\C_\infty \to \C_\infty$.
\end{lemma}

\begin{proof}
  The inverse of $f(z) = \frac{az + b}{cz+ d}$ is $g(z) = \frac{dz - b}{-cz + a}$, which we can check by composition both ways.
\end{proof}

\begin{prop}
  The M\"obius maps form a group $M$ under function composition. (The M\"obius group)
\end{prop}
\begin{proof}
  The group axioms are shown as follows:
  \begin{enumerate}[label=\arabic{*}.]
      \setcounter{enumi}{-1}
    \item If $f_1(z) = \frac{a_1z + b_1}{c_1z + d_1}$ and $f_2(z) = \frac{a_2z + b_2}{c_2 z + d_2}$, then $\displaystyle f_2\circ f_1 (z) = \frac{a_2\left(\frac{a_1z + b_1}{c_1z + d_1}\right) + b_2}{c_2\left(\frac{a_1z + b_1}{c_1z + d_1}\right) + d_2} = \frac{(a_1a_2 + b_2c_1)z + (a_2b_1 + b_2d_1)}{(c_2a_1 + d_2c_1)z + (c_2b_1 + d_1d_2)}$. Now we have to check that $ad - bc \not = 0$: we have $(a_1a_2 + b_2c_1)(c_2b_1 + d_1d_2) - (a_2b_1 + b_2d_1)(c_2a_1 + d_2c_1) = (a_1d_1 - b_1c_1)(a_2d_2 - b_2c_2)\not =0 $.

      (This works for $z\not= \infty, -\frac{d_1}{c_1}$. We have to manually check the special cases, which is simply yet more tedious algebra)
    \item The identity function is $1(z) = \frac{1z + 0}{0 + 1}$ which satisfies $ad - bc \not= 0$.
    \item We have shown above that $f^{-1}(z) = \frac{dz - b}{-cz + a}$ with $da - bc\not= 0$, which are also M\"obius maps
    \item Composition of functions is always associative
  \end{enumerate}
\end{proof}
$M$ is not abelian. e.g.\ $f_1(z) = 2z$ and $f_2(z) = z + 1$ are not commutative: $f_1\circ f_2(z) = 2z+2$ and $f_2\circ f_1(z) = 2z + 1$.

Note that the point at ``infinity'' is not special. $\infty$ is no different to any other point of the Riemann sphere. However, from the way we write down the M\"obius map, we have to check infinity specially. In this particular case, we can get quite far with conventions such as $\frac{1}{\infty} = 0$, $\frac{1}{0} = \infty$ and $\frac{a\cdot \infty}{c\cdot \infty} = \frac{a}{c}$.

Clearly $\frac{az + b}{cz + d} = \frac{\lambda az + \lambda b}{\lambda cz + \lambda d}$ for any $\lambda \not= 0$. So we do not have a unique representation of a map in terms of $a, b, c, d$. But $a, b, c, d$ does uniquely determine a M\"obius map.

\begin{prop}
  The map $\theta: \GL_2(\C)\to M$ sending $
  \displaystyle \begin{pmatrix}
    a & b\\
    c & d
  \end{pmatrix} \mapsto \frac{az + b}{cz + d}$ is a surjective group homomorphism.
\end{prop}

\begin{proof}
  Firstly, since the determinant $ad - bc$ of any matrix in $\GL_2(\C)$ is non-zero, it does map to a M\"obius map. This also shows that $\theta$ is surjective.

  We have previously calculated that
  \[
    \theta(A_2)\circ \theta(A_1) = \frac{(a_1a_2 + b_2c_1)z + (a_2b_1 + b_2d_1)}{(c_2a_1 + d_2c_1)z + (c_2b_1 + d_1d_2)} = \theta(A_2A_1)
  \]
  So it is a homomorphism.
\end{proof}

The kernel of $\theta$ is
\[
  \ker(\theta) = \left\{A\in \GL_2(\C): (\forall z)\,z = \frac{az + b}{cz + d}\right\}
\]
We can try different values of $z$: $z = \infty \Rightarrow c = 0$; $z = 0 \Rightarrow b = 0$; $z = 1\Rightarrow d = a$. So
\[
  \ker\theta = Z = \{\lambda I: \lambda \in \C, \lambda\not= 0\},
\]
where $I$ is the identity matrix and $Z$ is the centre of $\GL_2(\C)$.

By the isomorphism theorem, we have
\[
  M \cong \GL_2(\C)/Z
\]

\begin{defi}[Projective general linear group $\mathrm{PGL}_2(\C)$]
  (Non-examinable) The projective general linear group is
  \[
    \mathrm{PGL}_2(\C) = \GL_2(\C)/Z.
  \]
\end{defi}
Since $f_A = f_B$ iff $B = \lambda A$ for some $\lambda\not= 0$ (where $A, B$ are the corresponding matrices of the maps), if we restrict $\theta$ to $\SL_2(\C)$, we have $\left.\theta\right|_{\SL_2(\C)}: \SL_2(\C)\to M$ is also surjective. The kernel is now just $\{\pm I\}$. So
\[
  M \cong \SL_2(\C)/\{\pm I\} = \mathrm{PSL_2}(\C)
\]
Clearly $\mathrm{PSL}_2(\C)\cong \mathrm{PGL}_2(\C)$ since both are isomorphic to the M\"obius group.

\begin{prop}
  Every M\"obius map is a composite of maps of the following form:
  \begin{enumerate}
    \item Dilation/rotation: $f(z) = az$, $a\not= 0$
    \item Translation: $f(z) = z + b$
    \item Inversion: $f(z) = \frac{1}{z}$
  \end{enumerate}
\end{prop}
\begin{proof}
  Let $\frac{az + b}{cz + d}\in M$.

  If $c = 0$, i.e.\ $g(\infty) = \infty$, then $g(z) = \frac{a}{d}z + \frac{b}{d}$, i.e.
  \[
    z\mapsto \frac{a}{d} z\mapsto \frac{a}{d}z + \frac{b}{d}.
  \]
  If $c\not= 0$, let $g(\infty)=z_0$, Let $h(z) = \frac{1}{z - z_0}$. Then $hg(\infty) = \infty$ is of the above form. We have $h^{-1}(w) = \frac{1}{w} + z_0$being of type (iii) followed by (ii). So $g = h^{-1} (hg)$ is a composition of maps of the three forms listed above.

  Alternatively, with sufficient magic, we have
  \[
    z\mapsto z + \frac{d}{c} \mapsto \frac{1}{z + \frac{d}{c}} \mapsto -\frac{ad + bc}{c^2(z + \frac{d}{c})}\mapsto \frac{a}{c} -\frac{ad + bc}{c^2(z + \frac{d}{c})} = \frac{az + b}{cz + d}.\qedhere
  \]
\end{proof}
Note that the non-calculation method above can be transformed into another (different) composition with the same end result. So the way we compose a M\"obius map from the ``elementary'' maps are not unique.

\subsection{Fixed points of M\texorpdfstring{\"o}{o}bius maps}
\begin{defi}[Fixed point]
  A \emph{fixed point} of $f$ is a $z$ such that $f(z) = z$.
\end{defi}

We know that any M\"obius map with $c = 0$ fixes $\infty$. We also know that $z\to z + b$ for any $b\not= 0$ fixes $\infty$ only, where as $z\mapsto az$ for $a\not= 0, 1$ fixes $0$ and $\infty$. It turns out that you cannot have more than two fixed points, unless you are the identity.

\begin{prop}
  Any M\"obius map with at least 3 fixed points must be the identity.
\end{prop}

\begin{proof}
  Consider $f(z) = \frac{az + b}{cz + d}$. This has fixed points at those $z$ which satisfy $\frac{az + b}{cz + d} = z \Leftrightarrow cz^2 + (d - a)z - b = 0$. A quadratic has at most two roots, unless $c = b = 0$ and $d = a$, in which the equation just says $0 = 0$.

  However, if $c = b= 0$ and $d = a$, then $f$ is just the identity.
\end{proof}

\begin{prop}
  Any M\"obius map is conjugate to $f(z) = \nu z$ for some $\nu\not= 0$ or to $f(z) = z + 1$.
\end{prop}

\begin{proof}
  We have the surjective group homomorphism $\theta: \GL_2(\C) \to M$. The conjugacy classes of $\GL_2(\C)$ are of types
  \begin{align*}
    \begin{pmatrix}
      \lambda & 0\\
      0 & \mu
    \end{pmatrix} &\mapsto g(z) = \frac{\lambda z + 0}{0z + \mu} = \frac{\lambda}{\mu}z\\
    \begin{pmatrix}
      \lambda & 0\\
      0 & \lambda
    \end{pmatrix} &\mapsto g(z) = \frac{\lambda z + 0}{0z + \lambda} = 1 z\\
    \begin{pmatrix}
      \lambda & 1\\
      0 & \lambda
    \end{pmatrix} &\mapsto g(z) = \frac{\lambda z + 1}{\lambda} = z + \frac{1}{\lambda}
  \end{align*}
  But the last one is not in the form $z + 1$. We know that the last $g(z)$ can also be represented by $
  \begin{pmatrix}
    1 & \frac{1}{\lambda}\\
    0 & 1
  \end{pmatrix}$, which is conjugate to $
  \begin{pmatrix}
    1 & 1\\
    0 & 1
  \end{pmatrix}$ (since that's its Jordan-normal form). So $z + \frac{1}{\lambda}$ is also conjugate to $z + 1$.
\end{proof}

Now we see easily that (for $\nu \not= 0, 1$), $\nu z$ has $0$ and $\infty$ as fixed points, $z + 1$ only has $\infty$. Does this transfer to their conjugates?

\begin{prop}
  Every non-identity has exactly 1 or 2 fixed points.
\end{prop}

\begin{proof}
  Given $f\in M$ and $f\not= \mathrm{id}$. So $\exists h\in M$ such that $hfh^{-1}(z) = \nu{z}$. Now $f(w) = w \Leftrightarrow hf(w) = h(w) \Leftrightarrow hfh^{-1}(h(w)) = h(w)$. So $h(w)$ is a fixed point of $hfh^{-1}$. Since $h$ is a bijection, $f$ and $hfh^{-1}$ have the same number of fixed points.

  So $f$ has exactly $2$ fixed points if $f$ is conjugate to $\nu z$, and exactly 1 fixed point if $f$ is conjugate to $z + 1$.
\end{proof}
Intuitively, we can show that conjugation preserves fixed points because if we conjugate by $h$, we first move the Riemann sphere around by $h$, apply $f$ (that fixes the fixed points) then restore the Riemann sphere to its original orientation. So we have simply moved the fixed point around by $h$.

\subsection{Permutation properties of M\texorpdfstring{\"o}{o}bius maps}
We have seen that the M\"obius map with three fixed points is the identity. As a corollary, we obtain the following.

\begin{prop}
  Given $f, g\in M$. If $\exists z_1, z_2, z_3\in \C_{\infty}$ such that $f(z_i) = g(z_i)$, then $f = g$. i.e.\ every M\"obius map is uniquely determined by three points.
\end{prop}

\begin{proof}
  As M\"obius maps are invertible, write $f(z_i) = g(z_i)$ as $g^{-1}f(z_i) = z_i$. So $g^{-1}f$ has three fixed points. So $g^{-1}f$ must be the identity. So $f = g$.
\end{proof}

\begin{defi}[Three-transitive action]
  An action of $G$ on $X$ is called \emph{three-transitive} if the induced action on $\{(x_1, x_2, x_3)\in X^3: x_i\text{ pairwise disjoint}\}$, given by $g(x_1, x_2, x_3) = (g(x_1), g(x_2), g(x_3))$, is transitive.

  This means that for any two triples $x_1, x_2, x_3$ and $y_1, y_2, y_3$ of distinct elements of $X$, there exists $g\in G$ such that $g(x_i) = y_i$.

  If this $g$ is always unique, then the action is called \emph{sharply three transitive}
\end{defi}
This is a really weird definition. The reason we raise it here is that the M\"obius map satisfies this property.

\begin{prop}
  The M\"obius group $M$ acts sharply three-transitively on $\C_\infty$.
\end{prop}

\begin{proof}
  We want to show that we can send any three points to any other three points. However, it is easier to show that we can send any three points to $0, 1, \infty$.

  Suppose we want to send $z_1\to \infty, z_2\mapsto 0, z_3 \mapsto 1$. Then the following works:
  \[
    f(z) = \frac{(z - z_2)(z_3 - z_1)}{(z - z_1)(z_3 - z_2)}
  \]
  If any term $z_i$ is $\infty$, we simply remove the terms with $z_i$, e.g.\ if $z_1 = \infty$, we have $f(z) = \frac{z - z_2}{z_3 - z_2}$.

  So given also $w_1, w_2, w_3$ distinct in $\C_\infty$ and $g\in M$ sending $w_1\mapsto \infty, w_2\mapsto 0, w_3\mapsto 1$, then we have $g^{-1}f(z_i) = w_i$.

  The uniqueness of the map follows from the fact that a M\"obius map is uniquely determined by 3 points.
\end{proof}

3 points not only define a M\"obius map uniquely. They also uniquely define a line or circle. Note that on the Riemann sphere, we can think of a line as a circle through infinity, and it would be technically correct to refer to both of them as ``circles''. However, we would rather be clearer and say ``line/circle''.

We will see how M\"obius maps relate to lines and circles. We will first recap some knowledge about lines and circles in the complex plane.

\begin{lemma}
  The general equation of a circle or straight line in $\C$ is
  \[
    Az\bar z + \bar Bz + B\bar z + C = 0,
  \]
  where $A, C\in \R$ and $|B|^2 > AC$.
\end{lemma}
$A = 0$ gives a straight line. If $A \not= 0, B = 0$, we have a circle centered at the origin. If $C = 0$, the circle passes through 0.

\begin{proof}
  This comes from noting that $|z - B| = r$ for $r \in \R> 0$ is a circle; $|z - a| = |z - b|$ with $a\not= b $ is a line. The detailed proof can be found in Vectors and Matrices.
\end{proof}

\begin{prop}
  M\"obius maps send circles/straight lines to circles/straight lines. Note that it can send circles to straight lines and vice versa.

  Alternatively, M\"obius maps send circles on the Riemann sphere to circles on the Riemann sphere.
\end{prop}

\begin{proof}
  We can either calculate it directly using $w = \frac{az + b}{cz + d}\Leftrightarrow z = \frac{dw - b}{-cw + a}$ and substituting $z$ into the circle equation, which gives $A' w\bar w + \bar B' w + B'\bar w + C' = 0$ with $A', C'\in \R$.

  Alternatively, we know that each M\"obius map is a composition of translation, dilation/rotation and inversion. We can check for each of the three types. Clearly dilation/rotation and translation maps a circle/line to a circle/line. So we simply do inversion: if $w = z^{-1}$
  \begin{align*}
    &\; Az\bar z + \bar Bz + B\bar z + C = 0\\
    \Leftrightarrow &\; Cw\bar w + Bw + \bar B\bar w + A = 0\qedhere
  \end{align*}
\end{proof}

\begin{eg}
  Consider $f(z) = \frac{z - i}{z + i}$. Where does the real line go? The real line is simply a circle through $0, 1, \infty$. $f$ maps this circle to the circle containing $f(\infty) = 1$, $f(0) = -1$ and $f(1) = -i$, which is the unit circle.

  Where does the upper half plane go? We know that the M\"obius map is smooth. So the upper-half plane either maps to the inside of the circle or the outside of the circle. We try the point $i$, which maps to $0$. So the upper half plane is mapped to the inside of the circle.
\end{eg}
\subsection{Cross-ratios}
  Finally, we'll look at an important concept known as \emph{cross-ratios}. Roughly speaking, this is a quantity that is preserved by M\"obius transforms.

\begin{defi}[Cross-ratios]
  Given four distinct points $z_1, z_2, z_3, z_4\in \C_\infty,$ their \emph{cross-ratio} is $[z_1, z_2, z_3, z_4] = g(z_4)$, with $g$ being the unique M\"obius map that maps $z_1\mapsto \infty, z_2\mapsto 0, z_3\mapsto 1$. So $[\infty, 0, 1, \lambda] = \lambda$ for any $\lambda\not= \infty, 0, 1$. We have
  \[
    [z_1, z_2, z_3, z_4] = \frac{z_4 - z_2}{z_4 - z_1} \cdot \frac{z_3 - z_1}{z_3 - z_2}
  \]
  (with special cases as above).
\end{defi}
We know that this exists and is uniquely defined because $M$ acts sharply three-transitively on $\C_\infty$.

Note that different authors use different permutations of $1, 2, 3, 4$, but they all lead to the same result as long as you are consistent.

\begin{lemma}
  For $z_1, z_2, z_3, z_4\in \C_\infty$ all distinct, then
  \[
    [z_1, z_2, z_3, z_4] = [z_2, z_1, z_4, z_3] = [z_3, z_4, z_1, z_2] = [z_4, z_3, z_2, z_1]
  \]
  i.e.\ if we perform a double transposition on the entries, the cross-ratio is retained.
\end{lemma}

\begin{proof}
  By inspection of the formula.
\end{proof}

\begin{prop}
  If $f\in M$, then $[z_1, z_2, z_3, z_4] = [f(z_1), f(z_2), f(z_3), f(z_4)]$.
\end{prop}

\begin{proof}
  Use our original definition of the cross ratio (instead of the formula). Let $g$ be the unique M\"obius map such that $[z_1, z_2, z_3, z_4] = g(z_4) = \lambda$, i.e.
  \begin{align*}
    z_1 &\xmapsto{g} \infty\\
    z_2 &\mapsto 0\\
    z_3 &\mapsto 1\\
    z_4 &\mapsto \lambda
  \end{align*}
  We know that $gf^{-1}$ sends
  \begin{align*}
    f(z_1)\xmapsto{f^{-1}} z_1 &\xmapsto{g} \infty\\
    f(z_2)\xmapsto{f^{-1}} z_2 &\xmapsto{g} 0\\
    f(z_3)\xmapsto{f^{-1}} z_3 &\xmapsto{g} 1\\
    f(z_4)\xmapsto{f^{-1}} z_4 &\xmapsto{g} \lambda
  \end{align*}
  So $[f(z_1), f(z_2), f(z_3), f(z_4)] = gf^{-1}f(z_4) = g(z_4) = \lambda$.
\end{proof}

In fact, we can see from this proof that: given $z_1, z_2, z_3, z_4$ all distinct and $w_1, w_2, w_3, w_4$ distinct in $\C_\infty$, then $\exists f\in M$ with $f(z_i) = w_i$ iff $[z_1, z_2, z_3, z_4] = [w_1, w_2, w_3, w_4]$.

\begin{cor}
  $z_1, z_2, z_3, z_4$ lie on some circle/straight line iff $[z_1, z_2, z_3, z_4]\in \R$.
\end{cor}

\begin{proof}
  Let $C$ be the circle/line through $z_1, z_2, z_3$. Let $g$ be the unique M\"obius map with $g(z_1) = \infty$, $g(z_2) = 0$, $g(z_3) = 1$. Then $g(z_4) = [z_1, z_2, z_3, z_4]$ by definition.

  Since we know that M\"obius maps preserve circle/lines, $z_4\in C \Leftrightarrow g(z_4)$ is on the line through $\infty, 0, 1$, i.e.\ $g(z_4) \in \R$.
\end{proof}

\section{Projective line (non-examinable)}
We have seen in matrix groups that $\GL_2(\C)$ acts on $\C^2$, the column vectors. Instead, we can also have $\GL_2(\C)$ acting on the set of 1-dimensional subspaces (i.e.\ lines) of $\C^2$.

For any $\mathbf{v}\in \C^2$, write the line generated by $\mathbf{v}$ as $\bra \mathbf{v}\ket$. Then clearly $\bra \mathbf{v} \ket = \{\lambda \mathbf{v}: \lambda\in \C\}$. Now for any $A\in \GL_2(\C)$, define the action as $A\bra \mathbf{v}\ket = \bra A\mathbf{v}\ket$. Check that this is well-defined: for any $\bra \mathbf{v} \ket = \bra \mathbf{w}\ket$, we want to show that $\bra A\mathbf{v}\ket = \bra A\mathbf{w}\ket$. This is true because $\bra \mathbf{v} \ket = \bra \mathbf{w}\ket$ if and only if $\mathbf{w} = \lambda \mathbf{v}$ for some $\lambda\in \C\setminus\{0\}$, and then $\bra A\mathbf{w}\ket = \bra A\lambda\mathbf{v}\ket = \bra \lambda (A\mathbf{v})\ket = \bra A\mathbf{v}\ket$.

What is the kernel of this action? By definition the kernel has to fix all lines. In particular, it has to fix our magic lines generated by $\binom{1}{0}, \binom{0}{1}$ and $\binom{1}{1}$. Since we want $A\bra \binom{1}{0}\ket = \bra \binom{1}{0}\ket$, so we must have $A\binom{1}{0} = \binom{\lambda}{0}$ for some $\lambda$. Similarly, $A\binom{0}{1} = \binom{0}{\mu}$. So we can write $A =
\begin{pmatrix}
  \lambda & 0\\
  0 & \mu
\end{pmatrix}$. However, also need $A\bra \binom{1}{1}\ket = \bra\binom{1}{1}\ket$. Since $A$ is a linear function, we know that $A \binom{1}{1} = A \binom{1}{0} + A \binom{0}{1} = \binom{\lambda }{\mu}$. For the final vector to be parallel to $\binom{1}{1}$, we must have $\lambda = \mu$. So $A = \lambda I$ for some $I$. Clearly any matrix of this form fixes any line. So the kernel $Z = \{\lambda I: \lambda\in \C\setminus\{0\}\}$.

Note that every line is uniquely determined by its slope. For any $\mathbf{v} = (v_1, v_2), \mathbf{w} = (w_1, w_2)$, we have $\bra \mathbf{v}\ket = \bra \mathbf{w}\ket$ iff $z_1/z_2 = w_1/w_2$. So we have a one-to-one correspondence from our lines to $\C_\infty$, that maps $\bra \binom{z_1}{z_2}\ket\leftrightarrow z_1/z_2$.

Finally, for each $A\in \GL_2(\C)$, given any line $\bra \binom{z}{1}\ket$, we have
\[
  \begin{pmatrix}
    a & b\\
    c & d
  \end{pmatrix}
  \left\bra
  \begin{pmatrix}
    z\\1
  \end{pmatrix}\right\ket = \left\bra
  \begin{pmatrix}
    az + b\\
    cz + d
  \end{pmatrix}
  \right\ket \leftrightarrow \frac{az + b}{cz + d}
\]
So $\GL_2(\C)$ acting on the lines is just ``the same'' as the M\"obius groups acting on points.
\end{document}
